For students who start learning a programming language, bugs in the introductory program hinder the learning progress. Current introductory program judge systems merely provide a pass or fail by the percentage of passed test cases, while students may be unaware of potential defects hiding in their programs. It is helpful to provide a bug detection tool for them. However, state-of-the-art bug detection methods emphasize on precision and scalability, yet developing detection methods for numerous categories of defects is typically costly. In this paper, we first conducted an empirical study to mine common bug patterns, and found that (1) most bugs in such programs are simple; (2) bug patterns rely on specific programming tasks and thus be various. According to our findings, developing precise analysis methods for each bug pattern is unrealistic and unnecessary. Therefore, this paper further proposes a static detection framework to discover software bugs in order to ease the development of bug detection while maintaining a fair level of precision. Our framework is extensible by defining bug specification for bug patterns in a specific input format. The method is then applied to real-world introductory programs and successfully detect all bugs with a false positive rate of 25.8%.
In this paper, we focus on static detection methods, in
order to achieve a sound result and act as a complement
Introductory programming received increasing attention of program judgment systems. Unlike existing software
both in industry and academia. Such programs, devel- bugs or security vulnerabilities, bugs in introductory
prooped by students when taking introductory program- grams may have various patterns. To better understand
ming courses, are only validated by pre-defined test cases. bug patterns in such programs, this paper first conducts
However, passing all test cases does not guarantee that an empirical study of bug patterns that introductory
proprograms are free from bugs, leading to students mistak- grams commonly have. The results demonstrate that (1)
enly assume their programs are bug-free. And students most bugs in such programs are simple; (2) bug patterns
may introduce similar bugs (e.g., integer overflow) in rely on specific programming tasks and thus be various.
real-world programs, which may lead to serious conse- These results of empirical study show that existing
quences [
Earlier works predominately considered program anal- may introduce various kinds of bugs, which only occur
ysis for large-scale programs with complex bug patterns [2, in a certain category of programs. This raises a new
chal1, 3, 4, 5]. Carrybound [
In summary, this paper makes the following contributions: • An empirical study of student programming bugs
whose goal is to find common bug patterns in introductory programs. • A static detection framework that is extensible to
detect student programming bugs. • An implementation, DBI, which we use to bugs in existing bug datasets. Results show that (1) DBI is fast, taking on average less than 2 seconds to analyze all programs; (2) DBI is efective, giving on average less than 25.8% false-positive rate in real-world programs.
The remainder of this article is presented as the following.
Section 2 presents the detailed results of our empirical study. Section 3 details our analysis framework. Section 4 present our evaluation of DBI. Section 5 presents related works. Finally, section 6 gives the conclusion.
In this section, we show the setup and result of our empirical study about common bugs in introductory programs. 1 void secretFunction() { 2 printf("Danger zone!\n"); 3 } 4 void echo() { 5 char buffer[20]; 6 printf("Enter some text:\n"); 7 scanf("%s", buffer); 8 printf("You entered: %s\n", buffer); 9 } 10 int main() { 11 echo(); 12 return 0; 13 } Specifically, their methods are proposed to analyze large2.1. Learning from practice scale programs in an acceptable time budget while keeping high precision including flow-, context- and fieldSource code written by novice programmers is not free sensitive. Such methods are not suitable for detecting from bugs even though it passes the testing of the on- bugs in introductory programs because they require exline judge system. Such hidden bugs may make them perts to develop a new bug checker. To tackle this chalassume that their programs are bug-free. Therefore, in lenge, we present an extensible framework that can detect order to find such hidden bugs and design an extensible a new bug pattern with a little human cost. bug detection framework for these bugs, we conduct an empirical study to mine common bug patterns in existing bug datasets. Such bug patterns help us to understand 3. Detecting Bugs in Introductory how they are introduced, and how to detect them. programs
To survey the bug patterns, we manually inspect two kinds of programs in CodeForce1: the first kind passes test cases and the second one does not.
In this section, we first give a motivating example to show a buggy program. Then, we present an overview of DBI, followed by a detailed description of each component.
of memset Bufer overflow
Missing checks against external input
Missing checks after modification Difer ent precision of floating point data types
int a[16]; memset(a, 1, sizeof(a));
//a[0] is not 1.
int a[
aVal[i] = octs[i]; //Buffer overflow
struct node *ptr = head;
for (; ptr != NULL; ptr = ptr->next)
free(ptr);
//ptr is freed when accessing ptr->next.
char str[
n=n.substr(1); float a=0.1+0.2; if(a==0.1+0.2) return true; return false; double sap[100] = 3.14e10; int n = 100; double sum, sqresum ; for ( int i; i < n; i ++) { sum += sap [i ]; sqresum += sap [i] * sap [i ]; } return ( sqresum - sum*sum/n) / n; // Should be zero but is 9.761004 × 1018 if(a+b<=c||a+c<=b||c+b<=a)
return true; // Incorrect result when
a, b, c are all INT_MAX
unsigned int a = 0; int b = -1;
if((a+b)>=0) return true;
return false;
// Should return fale but it returns true.
scanf("%d", &x); x = x - 5;
int y = 100/x; // x may be zero.
int *p = NULL; int q = *p;
// Dereferencing p leads to crash.
int a[
after modification.
Replace the condition with. abs(a-b) < epsilon
Change to (b+10)%10.
of 4 main components: CFG Construction, Pre-Analysis, notes a bug pattern, denotes directions (forward or Analysis Mode, and Post-Analysis. backward), indicates whether all paths (i.e., forall) or
CFG Construction produces inter-procedure CFGs for only one path (i.e., exists) should satisfy , and is a
programs. The reaming three components, acting as constraint whose violation will lead to a bug report. The
the main procedure, perform the analysis against a bug four elements are used for Pre-Analysis ( ), Analysis
specification. Its intuition is straightforward: we first Mode ( and ), and Post-Analysis (), respectively.
search instructions that satisfy a pre-defined bug pattern. and are written according to the syntax of a
proThen for each of these instructions (denoted by ), gramming language in first order logic [
The inputs of the framework are the source code of a program and bug specification. The bug specification The first component in the framework is CFG Construcis a 4-tuple: := <, , , >, where de- tion, which is a preprocessing step that generates control 3.4. CFG Construction lfow graphs (CFG) for the input source code. Specifically, along the ICFG. For each of these instructions (denoted as it parses the source code, constructs CFG for each func- ), we construct a path (denoted as ℎ) from tion, and connects each CFG to an inter-procedure CFG to , then check whether satisfies condition . (ICFG). Worth noting that we do not perform alias analy- If it does and the analysis mode is exists, then we sis in this step because our method naturally traces all finish the analysis. If the analysis mode is forall, then possible aliases when analyzing bugs in each path. we continue analyzing other paths until all paths satisfy condition or some path fails to meet . If the condition 3.5. Pre-Analysis is satisfied in at least one path ( resp., all paths) in exists (resp., forall), we will not report the bug. Otherwise, we The component identifies a set of buggy instructions de- regard as a buggy instruction. ifned by . We analyze each instruction in the ICFG to For the example in Figure 1, we will not report the determine whether the instruction meets the bug pattern. instruction if each path that starts from the (i.e., If so, the instruction is denoted as and the variable scanf at line 7) has corresponding that satisfies that saves the buggy content is denoted as . := ∈ .. In other words, we
For example, in order to detect the bug in Figure 1, will not report the bug if (i.e., buffer) in is we design := = ∧ . = . checked in a condition (e.g., a if branch), regardless of It means that we will find all instructions with scanf whether the condition is correct or not. because input from users is regarded as unsafe. Therefore, a function call scanf("%s", buffer); is and its 3.8. Outputs is buffer because the buffer saves the content of unsafe input.
Forward/Backward. indicates the direction of our analysis: forward or backward. Forward (resp., Backward) means analyzing the instructions after (resp., before) the bug pattern. The reason is to analyze two kinds of bugs: 4.1. Implementation the first kind occurs when condition is before the bug pattern while the second one is after the bug pattern.
For example, given a user input, we check whether the input is valid and discard invalid input. Such checks, if exist, only be valid after the bug pattern (i.e., a variable provided by users).
Our method is implemented by Clang2, in order to use its basic analysis infrastructure such as parsing ASTs, constructing CFGs, analyzing instructions and analyzing paths.
Forall/Exists. indicates whether all paths or at least 4.2. Implemented bug specifications one path should satisfy . The intuition of is because one situation only requires that at least one path (denoted as ℎ) that satisfies condition to avoid introducing the bugs. In contrast, the other situation requires that all paths should satisfy condition to avoiding introducing the bugs. Therefore, we design forall and exists modes to support the two situations.
For example, to detect the bug in Figure 1, we should check that all paths after the scanf should check whether the input string is valid. So is forward and is forall We design bug specifications and apply it to existing introductory programs. As shown in Table 2, we implement seven bug specifications for bugs in Table 1. We explain the first two specifications in detail: Check string length after modification. The specification is := <, , , > where := [] ( is an integer variable), is set to backward, is forall, and := .() > 1. An example of the buggy statement is while (n[0]==’0’ && n.size()>1) n=n.substr(1); . The correct one should swap the two predicates, resulting in while (n.size()>1 && n[0]==’0’) n=n.substr(1);.
The component checks whether variable in each Modulo negative number. As for detecting Modulo instruction that flows from satisfies constraint . operation with negative numbers, the bug specification is the buggy instruction from the Pre-Analysis. For is := < > where := % without , , each , we analyze instructions after (or before) and . ( + )% is deemed to satisfy the , but (% + )% is deemed as a bug-free statement because % + must be positive. caused by imprecise . The instruction in the falsepositive program matching the is = %10; , but the data type of num is unsigned int. To get rid of this, we need to refine bug specification to meet more situations.
We evaluated DBI against synthetic and real-world
programs. First, we apply it to existing introductory pro- Table 4 depicts the results of our method in analyzing
realgrams in IntroClass [
Table 3 depicts the results of our method in analyzing 4
introductory programs. In all 4 programs, our method, 5.1. Static analysis
which achieves an average 25% false-positive rate, is pre- We found two strands of static methods, the first one
cise in detecting bugs. We found that one reason of analyzes programs with theoretical guarantee [
For java introductory programs, Nghi et al.. developed
a static analysis framework ELP (Learning to Program)
based on good programming practice experience [
This paper first conducts an empirical study showing common bug patterns written by novice programmers. However, it also finds that such bug patterns are usually simple and easy to detect but the bug patterns may rely on specific programming tasks. Therefore, to easily develop a new bug checker while keeping a reasonable precision, this paper also presents a bug detection framework for introductory programs. This method reports bugs by checking whether variables that flow from a bug pattern do not meet an expected constraint. In addition, we implement a prototype tool and conduct a case study