Computing and Information Systems - Theses
Permanent URI for this collection
Search Results
1 - 1 of 1
-
ItemDynamic Symbolic Execution with Descriptive and Prescriptive Relations( 2019)Static analysis and systematic software testing are two fundamental techniques that aim to ensure software quality. Recently, there has been an obvious interest in exploiting the strengths of these two techniques to work together to attain their goals effectively. Dynamic Symbolic Execution (DSE) is an example of a unique collaboration between these two techniques. It is a non-standard execution mechanism which, loosely, executes a program symbolically and, simultaneously, on concrete input. Thus, DSE simultaneously and symbolically follows all possible executable paths in the program with a goal of achieving high coverage for some chosen definition of coverage. In practice, the massive number of program paths to be explored and the number of constraints to be solved hinder scalability of DSE. This problem is referred to as path explosion. Path explosion can be caused by nested calls, loops and conditionals, and particularly loops whose termination depend on program inputs. The problem is made worse in the presence of indirect relations between symbolic and non-symbolic variables in the program under tests. This can significantly affect DSE efficiency. In addition, automated testing is not widely adopted in practice due to the lack of test oracles. Hence, DSE is mainly applied as a fuzzing technique, in which a large number of test inputs are generated to detect some generic errors (e.g., buffer overflows or security violations). The approach does not reveal faults that are domain specific, thus; its fault detection effectiveness in functional testing is not clear. In this thesis, we propose that understanding available static and dynamic analysis techniques, and leveraging their strength to complement each other is an effective approach to mitigate path explosion problem in DSE. We propose a conceptual framework for a comparative analysis of program analysis techniques, and we use it to define proposed techniques in this thesis to support DSE. Having considered this view, our research aims at improving DSE efficiency and fault detection effectiveness by exploiting program relational information about the values that variables take at run-time. This information is obtained from available static and dynamic analysis techniques at two levels. First, we employ “descriptive relations” about program internal behaviour to support DSE in order to tackle path explosion caused mainly by loops. We obtain these relations from static analysis by abstract interpretation; we use its ability to approximate program run-time states to compute interesting properties including relations between program variables that could be missed in DSE. Second, we suggest enhancing fault detection effectiveness of DSE, in the context of functional testing, by using domain specific relations that prescribe how inputs and outputs should be related. These “prescriptive relations” leverage constraints of the underlying domain to identify faults in the program under test as a form of partial oracles. To achieve this goal, we integrate DSE with metamorphic testing, a technique that employ domain specific relations to alleviate the absence of a test oracle.