Multi-Platform Binary Program Testing Using Concolic Execution

Examensarbete för masterexamen
Master Thesis
Siewertsen, Eike
In today's world, computer systems have long since made the move from the desktop to numerous locations in the form of routers, intelligent light bulbs, electricity meters and more. These devices are referred to as \embedded devices", because they are generally smaller, less powerful versions of their PC counterparts. These computers have lower memory and CPU performance requirements, leading to challenges in creating software for such devices: resource constraints encourage the use of unsafe programming languages, which in turn promotes an environment that can lead to mistakes or unintended side-effects of the created program. Some of these errors open up vulnerabilities that can be abused, causing the program to perform unintended actions or giving the actors control over the software and consequently the device. For the owner of the device, this can lead to annoyances in the case of an intelligent light bulb, to real, economic and physical damage in the case of devices in a critical infrastructure. It is therefore necessary for a manufacturer of such devices to ensure the presence of steps in the development process that ensure the software conforms rigorously to the speci cation. Aside from development guidelines for writing program code, and the choice of safe programming languages, the actual testing of the nished application can discover critical errors before the release of the program or device. Testing applications can be time-intensive work due to the need for proper test cases that elicit the entirety of the program's functionality. For this reason, a suite of applications exists called \fuzzers", that automatically generate exhaustive test cases for programs. In this thesis we present an automated system for generating such test cases for a program. Unlike most fuzzing engines, our solution can function without the need for its source code, and it supports multiple architectures. We use a technique called \concolic execution" to ensure that each newly generated test case causes the program to exhibit new behavior. With this, we intend to be able to cover all parts of the original program much faster than humans could manually write test cases and better than completely randomly generated inputs. Our results are promising in that they show that we can produce exhaustive test cases that reliably cause a program to follow unique execution paths. This accuracy comes with a greatly increased execution cost, however, causing our current solution to require further work to handle larger programs. Nevertheless, we can show that in isolation, our solution outperforms an advanced fuzzer in the case of complicated branch conditions. We conclude that the area of our thesis shows promising results, and that future work can greatly improve the result by removing some of the current limitations and improving performance.
Data- och informationsvetenskap, Informations- och kommunikationsteknik, Computer and Information Science, Information & Communication Technology
Arkitekt (konstruktör)
Geografisk plats
Byggnad (typ)
Teknik / material