(Press-News.org) Integer overflows are one of the most common bugs in computer programs -- not only causing programs to crash but, even worse, potentially offering points of attack for malicious hackers. Computer scientists have devised a battery of techniques to identify them, but all have drawbacks.
This month, at the Association for Computing Machinery's International Conference on Architectural Support for Programming Languages and Operating Systems, researchers from MIT's Computer Science and Artificial Intelligence Laboratory (CSAIL) will present a new algorithm for identifying integer-overflow bugs. The researchers tested the algorithm on five common open-source programs, in which previous analyses had found three bugs. The new algorithm found all three known bugs -- and 11 new ones.
The variables used by computer programs come in a few standard types, such as floating-point numbers, which can contain decimals; characters, like the letters of this sentence; or integers, which are whole numbers. Every time the program creates a new variable, it assigns it a fixed amount of space in memory.
If a program tries to store too large a number at a memory address reserved for an integer, the operating system will simply lop off the bits that don't fit. "It's like a car odometer," says Stelios Sidiroglou-Douskos, a research scientist at CSAIL and first author on the new paper. "You go over a certain number of miles, you go back to zero."
In itself, an integer overflow won't crash a program; in fact, many programmers use integer overflows to perform certain types of computations more efficiently. But if a program tries to do something with an integer that has overflowed, havoc can ensue. Say, for instance, that the integer represents the number of pixels in an image the program is processing. If the program allocates memory to store the image, but its estimate of the image's size is off by several orders of magnitude, the program will crash.
Charting a course
Any program can be represented as a flow chart -- or, more technically, a graph, with boxes that represent operations connected by line segments that represent the flow of data between operations. Any given program input will trace a single route through the graph. Prior techniques for finding integer-overflow bugs would start at the top of the graph and begin working through it, operation by operation.
For even a moderately complex program, however, that graph is enormous; exhaustive exploration of the entire thing would be prohibitively time-consuming. "What this means is that you can find a lot of errors in the early input-processing code," says Martin Rinard, an MIT professor of computer science and engineering and a co-author on the new paper. "But you haven't gotten past that part of the code before the whole thing poops out. And then there are all these errors deep in the program, and how do you find them?"
Rinard, Sidiroglou-Douskos, and several other members of Rinard's group -- researchers Eric Lahtinen and Paolo Piselli and graduate students Fan Long, Doekhwan Kim, and Nathan Rittenhouse -- take a different approach. Their system, dubbed DIODE (for Directed Integer Overflow Detection), begins by feeding the program a single sample input. As that input is processed, however -- as it traces a path through the graph -- the system records each of the operations performed on it by adding new terms to what's known as a "symbolic expression."
"These symbolic expressions are complicated like crazy," Rinard explains. "They're bubbling up through the very lowest levels of the system into the program. This 32-bit integer has been built up of all these complicated bit-level operations that the lower-level parts of your system do to take this out of your input file and construct those integers for you. So if you look at them, they're pages long."
Trigger warning
When the program reaches a point at which an integer is involved in a potentially dangerous operation -- like a memory allocation -- DIODE records the current state of the symbolic expression. The initial test input won't trigger an overflow, but DIODE can analyze the symbolic expression to calculate an input that will.
The process still isn't over, however: Well-written programs frequently include input checks specifically designed to prevent problems like integer overflows, and the new input, unlike the initial input, might fail those checks. So DIODE seeds the program with its new input, and if it fails such a check, it imposes a new constraint on the symbolic expression and computes a new overflow-triggering input. This process continues until the system either finds an input that can pass the checks but still trigger an overflow, or it concludes that triggering an overflow is impossible.
If DIODE does find a trigger value, it reports it, providing developers with a valuable debugging tool. Indeed, since DIODE doesn't require access to a program's source code but works on its "binary" -- the executable version of the program -- a program's users could run it and then send developers the trigger inputs as graphic evidence that they may have missed security vulnerabilities.
INFORMATION:
MADISON, Wis. -- By figuring out how to precisely order the molecules that make up what scientists call organic glass -- the materials at the heart of some electronic displays, light-emitting diodes and solar cells -- a team of chemists from the University of Wisconsin-Madison has set the stage for more efficient and sturdier portable electronic devices and possibly a new generation of solar cells based on organic materials.
Writing this week (March 23, 2015) in the Proceedings of the National Academy of Sciences (PNAS), a team led by UW-Madison chemistry Professor Mark ...
Jupiter may have swept through the early solar system like a wrecking ball, destroying a first generation of inner planets before retreating into its current orbit, according to a new study published March 23 in Proceedings of the National Academy of Sciences. The findings help explain why our solar system is so different from the hundreds of other planetary systems that astronomers have discovered in recent years.
"Now that we can look at our own solar system in the context of all these other planetary systems, one of the most interesting features is the absence of planets ...
'Attractive' male birds that mate with many females aren't passing on the best genes to their offspring, according to new UCL research which found promiscuity in male birds leads to small, genetic faults in the species' genome.
Although minor, these genetic flaws may limit how well future generations can adapt to changing environments.
The study, published this week in Proceedings of the National Academy of Sciences and funded by the European Research Council, shows for the first time the power of sexual selection - where some individuals are better at securing mates ...
Leprosy is a chronic infection of the skin, peripheral nerves, eyes and mucosa of the upper respiratory tract, affecting over a quarter million people worldwide. Its symptoms can be gruesome and devastating, as the bacteria reduce sensitivity in the body, resulting in skin lesions, nerve damage and disabilities. Until recently, leprosy was attributed to a single bacterium, Mycobacterium leprae; we now suspect that its close relative, Mycobacterium lepromatosis, might cause a rare but severe form of leprosy. Scientists at École Polytechnique Fe?de?rale de Lausanne (EPFL) ...
Western U.S. forests killed by the mountain pine beetle epidemic are no more at risk to burn than healthy Western forests, according to new findings by the University of Colorado Boulder that fly in the face of both public perception and policy.
The CU-Boulder study authors looked at the three peak years of Western wildfires since 2002, using maps produced by federal land management agencies. The researchers superimposed maps of areas burned in the West in 2006, 2007 and 2012 on maps of areas identified as infested by mountain pine beetles.
The area of forests burned ...
A molecule that prevents Type 1 diabetes in mice has provoked an immune response in human cells, according to researchers at National Jewish Health and the University of Colorado. The findings, published online in the Proceedings of the National Academy of Sciences, suggest that a mutated insulin fragment could be used to prevent Type 1 diabetes in humans.
"The incidence of Type 1 diabetes is increasing dramatically," said John Kappler, PhD, professor of Biomedical Research at National Jewish Health. "Our findings provide an important proof of concept in humans for a ...
Non-native plants are commonly listed as invasive species, presuming that they cause harm to the environment at both global and regional scales. New research by scientists at the University of York has shown that non-native plants - commonly described as having negative ecological or human impacts - are not a threat to floral diversity in Britain.
Using repeat census field survey data for British plants from 1990 and 2007, Professor Chris Thomas and Dr Georgina Palmer from the Department of Biology at York analysed changes in the cover and diversity of native and non-native ...
A 60-year-old maths problem first put forward by Nobel laureate Enrico Fermi has been solved by researchers at the University of East Anglia, the Università degli Studi di Torino (Italy) and the Rensselaer Polytechnic Institute (US).
In 1955, a team of physicists, computer scientists and mathematicians led by Fermi used a computer for the first time to try and solve a numerical experiment.
The outcome of the experiment wasn't what they were expecting, and the complexity of the problem underpinned the then new field of non-linear physics and paved the way for six ...
Researchers at Carnegie Mellon University who develop snake-like robots have picked up a few tricks from real sidewinder rattlesnakes on how to make rapid and even sharp turns with their undulating, modular device.
Working with colleagues at the Georgia Institute of Technology and Zoo Atlanta, they have analyzed the motions of sidewinders and tested their observations on CMU's snake robots. They showed how the complex motion of a sidewinder can be described in terms of two wave motions - vertical and horizontal body waves - and how changing the phase and amplitude of ...
Troy, N.Y. - A team of researchers, including Rensselaer professor Morgan Schaller, has used mathematical modeling to show that continental erosion over the last 40 million years has contributed to the success of diatoms, a group of tiny marine algae that plays a key role in the global carbon cycle. The research was published today in the Proceedings of the National Academy of Sciences.
Diatoms consume 70 million tons of carbon from the world's oceans daily, producing organic matter, a portion of which sinks and is buried in deep ocean sediments. Diatoms account for over ...
