{"id":3522,"date":"2015-03-24T06:29:22","date_gmt":"2015-03-24T06:29:22","guid":{"rendered":"http:\/\/revoscience.com\/en\/?p=3522"},"modified":"2015-03-24T06:29:22","modified_gmt":"2015-03-24T06:29:22","slug":"better-debugger","status":"publish","type":"post","link":"https:\/\/www.revoscience.com\/en\/better-debugger\/","title":{"rendered":"Better debugger"},"content":{"rendered":"

System to automatically find a common type of programming bug significantly outperforms its predecessors.<\/strong><\/em><\/span><\/p>\n

\"Integer<\/a>
Integer overflows occur when a computer tries to store too large a number in the memory space reserved for it. The leading digits are discarded \u2014 much as they are when a car odometer turns over.
Image: Jose-Luis Olivares\/MIT<\/figcaption><\/figure>\n

CAMBRIDGE, Mass. —\u00a0Integer overflows are one of the most common bugs in computer programs \u2014 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.<\/span><\/p>\n

This month, at the Association for Computing Machinery\u2019s International Conference on Architectural Support for Programming Languages and Operating Systems, researchers from MIT\u2019s 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 \u2014 and 11 new ones.<\/span><\/p>\n

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.<\/span><\/p>\n

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\u2019t fit. \u201cIt\u2019s like a car odometer,\u201d says Stelios Sidiroglou-Douskos, a research scientist at CSAIL and first author on the new paper. \u201cYou go over a certain number of miles, you go back to zero.\u201d<\/span><\/p>\n

In itself, an integer overflow won\u2019t 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\u2019s size is off by several orders of magnitude, the program will crash.<\/span><\/p>\n

Charting a course<\/strong><\/span><\/p>\n

Any program can be represented as a flow chart \u2014 or, more technically, a\u00a0graph<\/span><\/a>, 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.<\/span><\/p>\n

For even a moderately complex program, however, that graph is enormous; exhaustive exploration of the entire thing would be prohibitively time-consuming. \u201cWhat this means is that you can find a lot of errors in the early input-processing code,\u201d says Martin Rinard, an MIT professor of computer science and engineering and a co-author on the new paper. \u201cBut you haven\u2019t 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?\u201d<\/span><\/p>\n

Rinard, Sidiroglou-Douskos, and several other members of Rinard\u2019s group \u2014 researchers Eric Lahtinen and Paolo Piselli and graduate students Fan Long, Doekhwan Kim, and Nathan Rittenhouse \u2014 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 \u2014 as it traces a path through the graph \u2014 the system records each of the operations performed on it by adding new terms to what\u2019s known as a \u201csymbolic expression.\u201d<\/span><\/p>\n

\u201cThese symbolic expressions are complicated like crazy,\u201d Rinard explains. \u201cThey\u2019re 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\u2019re pages long.\u201d<\/span><\/p>\n

Trigger warning<\/strong><\/span><\/p>\n

When the program reaches a point at which an integer is involved in a potentially dangerous operation \u2014 like a memory allocation \u2014 DIODE records the current state of the symbolic expression. The initial test input won\u2019t trigger an overflow, but DIODE can analyze the symbolic expression to calculate an input that will.<\/span><\/p>\n

The process still isn\u2019t 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.<\/span><\/p>\n

If DIODE does find a trigger value, it reports it, providing developers with a valuable debugging tool. Indeed, since DIODE doesn\u2019t require access to a program\u2019s source code but works on its \u201cbinary\u201d \u2014 the executable version of the program \u2014 a program\u2019s users could run it and then send developers the trigger inputs as graphic evidence that they may have missed security vulnerabilities.<\/span><\/p>\n","protected":false},"excerpt":{"rendered":"

System to automatically find a common type of programming bug significantly outperforms its predecessors. CAMBRIDGE, Mass. —\u00a0Integer overflows are one of the most common bugs in computer programs \u2014 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 […]<\/p>\n","protected":false},"author":6,"featured_media":3523,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[47,17],"tags":[],"class_list":["post-3522","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-it","category-research"],"featured_image_urls":{"full":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/03\/MIT-Integer-Over-01.jpg",639,426,false],"thumbnail":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/03\/MIT-Integer-Over-01-150x150.jpg",150,150,true],"medium":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/03\/MIT-Integer-Over-01-300x200.jpg",300,200,true],"medium_large":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/03\/MIT-Integer-Over-01.jpg",639,426,false],"large":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/03\/MIT-Integer-Over-01.jpg",639,426,false],"1536x1536":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/03\/MIT-Integer-Over-01.jpg",639,426,false],"2048x2048":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/03\/MIT-Integer-Over-01.jpg",639,426,false],"ultp_layout_landscape_large":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/03\/MIT-Integer-Over-01.jpg",639,426,false],"ultp_layout_landscape":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/03\/MIT-Integer-Over-01.jpg",639,426,false],"ultp_layout_portrait":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/03\/MIT-Integer-Over-01.jpg",600,400,false],"ultp_layout_square":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/03\/MIT-Integer-Over-01.jpg",600,400,false],"newspaper-x-single-post":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/03\/MIT-Integer-Over-01.jpg",639,426,false],"newspaper-x-recent-post-big":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/03\/MIT-Integer-Over-01.jpg",540,360,false],"newspaper-x-recent-post-list-image":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/03\/MIT-Integer-Over-01.jpg",95,63,false],"web-stories-poster-portrait":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/03\/MIT-Integer-Over-01.jpg",639,426,false],"web-stories-publisher-logo":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/03\/MIT-Integer-Over-01.jpg",96,64,false],"web-stories-thumbnail":["https:\/\/www.revoscience.com\/en\/wp-content\/uploads\/2015\/03\/MIT-Integer-Over-01.jpg",150,100,false]},"author_info":{"info":["Amrita Tuladhar"]},"category_info":"IT<\/a> Research<\/a>","tag_info":"Research","comment_count":"0","_links":{"self":[{"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/posts\/3522","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/users\/6"}],"replies":[{"embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/comments?post=3522"}],"version-history":[{"count":0,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/posts\/3522\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/media\/3523"}],"wp:attachment":[{"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/media?parent=3522"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/categories?post=3522"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.revoscience.com\/en\/wp-json\/wp\/v2\/tags?post=3522"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}