What is a Valuable Input for Software Testing
Recently I spent some time reading the papers that describe the input synthesis. The idea is from the paper "Synthesizing Racy Tests" from PLDI'15.
As I am designing the bug detection tool, we always assume we already have the input that can trigger the bug. It looks strange that why not just run the program under the buggy input to expose the bug. The reason is that the hardest part in software is nondeterminism. Even under the buggy input, the bug is not guaranteed to occur every time.
Another thing is that the automated detection toolchain has three part: input generation, detection, and validation. I found that now the validation part begins to move the detection in order to make the tool more solid. And I feel it could be a trend that the detection move to the input generation part. Because the input generation has a lot of information that is useful for detection. The input analysis makes the detection more intelligent.
After reading several input synthesis papers, the most confusing thing is that all the tools only work for the library code. The technical challenges for whole system testing include that the function or module cannot be invoked easily unlike calling a function in lib form another thread. But I do not feel this is the fundamental challenge for applying the input synthesis for real system. I think we need a higher abstract to re-consider the real system input synthesis.
One more thing is context construction. For convincing people believe the input is buggy, the tool usually provides the context to expose the bug under certain input. It looks like necessary. But there is no specific definition for this problem. I just feel like this problem should no be solved in such a brute force(like searching or SAT) approach.
Th first paper is "Synthesizing Racy Tests". The general idea is that it searches the unprotected memory access to construct data race input. The interesting thing is that unprotected means one memory access is not protected by a lock that is associated with the accessed memory. It could be protected by other locks.
The second paper is "Directed Synthesis of Failing Concurrent Executions". It is about how to generate an input that ensures one instruction must happen in the runtime. It is more powerful and can be applied in multiple scenarios. The idea is keeping come up a new thread to execute a function that changes the environment to make sure the if-block related the pointed instruction enter the desired branch.
The third paper is "Coverage-driven test code generation for concurrent classes". This paper is related unusual bad/good. To use this tool, I need to specify a partial order of the subset of all the instructions. Then it gonna to search the input that satisfies this partial order. What it did is REALLY search. It starts with random test and tries to combine the random test together to generate the concurrent test. Then it uses happen-before analysis to check if the partial order could be satisfied.
The fourth paper is "Type-Aware Concolic Testing of JavaScript Programs". Before I read this paper, I even do not know what is concolic testing. It is based on symbolic execution. Symbolic execution can figure out all the condition for reaching a specific execution path. The problem about concolic testing is that it needs to guess undefined for parameters. But this guess maybe redundant. For example, it only needs to guess one undefined for the statement "z=x+y" instead of three. The tool also analyzes the context to get some information about the parameters. Then the tool does not need to guess too much for the constrained parameters.
The last paper is "Directed Test Generation to Detect Loop Inefficiencies". The idea about this paper is pretty simple. It just detects the nested loop. It locates the nested loop through the random tests. Then it finds the methods that can change the boundaries of loops. In the end, it can create a context that contains two large nested loops.
Another thing is that the automated detection toolchain has three part: input generation, detection, and validation. I found that now the validation part begins to move the detection in order to make the tool more solid. And I feel it could be a trend that the detection move to the input generation part. Because the input generation has a lot of information that is useful for detection. The input analysis makes the detection more intelligent.
After reading several input synthesis papers, the most confusing thing is that all the tools only work for the library code. The technical challenges for whole system testing include that the function or module cannot be invoked easily unlike calling a function in lib form another thread. But I do not feel this is the fundamental challenge for applying the input synthesis for real system. I think we need a higher abstract to re-consider the real system input synthesis.
One more thing is context construction. For convincing people believe the input is buggy, the tool usually provides the context to expose the bug under certain input. It looks like necessary. But there is no specific definition for this problem. I just feel like this problem should no be solved in such a brute force(like searching or SAT) approach.
Th first paper is "Synthesizing Racy Tests". The general idea is that it searches the unprotected memory access to construct data race input. The interesting thing is that unprotected means one memory access is not protected by a lock that is associated with the accessed memory. It could be protected by other locks.
The second paper is "Directed Synthesis of Failing Concurrent Executions". It is about how to generate an input that ensures one instruction must happen in the runtime. It is more powerful and can be applied in multiple scenarios. The idea is keeping come up a new thread to execute a function that changes the environment to make sure the if-block related the pointed instruction enter the desired branch.
The third paper is "Coverage-driven test code generation for concurrent classes". This paper is related unusual bad/good. To use this tool, I need to specify a partial order of the subset of all the instructions. Then it gonna to search the input that satisfies this partial order. What it did is REALLY search. It starts with random test and tries to combine the random test together to generate the concurrent test. Then it uses happen-before analysis to check if the partial order could be satisfied.
The fourth paper is "Type-Aware Concolic Testing of JavaScript Programs". Before I read this paper, I even do not know what is concolic testing. It is based on symbolic execution. Symbolic execution can figure out all the condition for reaching a specific execution path. The problem about concolic testing is that it needs to guess undefined for parameters. But this guess maybe redundant. For example, it only needs to guess one undefined for the statement "z=x+y" instead of three. The tool also analyzes the context to get some information about the parameters. Then the tool does not need to guess too much for the constrained parameters.
The last paper is "Directed Test Generation to Detect Loop Inefficiencies". The idea about this paper is pretty simple. It just detects the nested loop. It locates the nested loop through the random tests. Then it finds the methods that can change the boundaries of loops. In the end, it can create a context that contains two large nested loops.
Comments
Post a Comment