-We discuss static and dynamic methods of the code analysis. A new approach to the static analysis method based on command flow graphs is presented. Practical cases and implementations of this dataflow approach are given.
INTRODUCTION
IT-based solutions are currently used everywhere, and
significant problems are represented by both internal software
errors of the information systems, and malicious source code
implemented in the information system software. The
consequences of both problems lead to violation of access,
integrity and confidentiality of the processed information,
which can result in financial and reputational losses of the
business. This is a reason of growing financial losses over the
last few years. High quality and failure-free operation of the
source code is a burning issue of the software industry. Ever
growing complexity of the software complexes, their use in the
management and control systems of the government and the
industrial production require continuous upgrading of the
software testing and control methods [
II.
ANALYSIS
Upon the whole, the testing methods used in the audit of the
software systems security may be divided into two groups:
static methods (structural testing) and dynamic methods
(functional testing). Static methods of the code analysis, which
do not require running of the analysed code for its operation,
allow for full or partial automation [
Dynamic software analysis is a method of analysis that
stipulates program running on real or virtual processor [
III.
The approach that is called signature analysis implies the
search for software defects in the software code by comparing
code fragments with the samples from the database of templates
(signatures) of the security defects. Depending on the method
for correlating fragments of the code to the template, and the
intermediate representation in use, there may be algorithms of
searching for a substring in the string, and query language for
structured information (for instance, XQuery for XML), or
specially designed methods of correlation, but in each case each
of the signatures represents the decision procedure, which
employs various presence bits of potentially harmful structure.
[
Improvement of the operational qualities of the static code
analysis is mainly related to minimizing the number of “false
positives” while preserving maximum fullness of the list of the
types of potentially harmful structures [
The field for designing means of static analysis is now
actively developing: new directions of analysis do not force out
the reputable approaches, on the contrary, they complement
them by integrating the advantages of the predecessors. For
instance, such approach as dataflow analysis may compensate
for the drawbacks of the template-based code defect search,
which does not allow for high quality of identification of
SQL, Path-, XSS-injections, and other types of code injections,
however, it will require large RAM and computing resources of
the processor [
An interesting manifestation of symbiosis of the analysis
methods is when potentially harmful structures, which have
been initially identified by the customary signature method is
supported by the automated method using highly-specialized,
costly, but efficient procedures [
IV.
DATAFLOW ANALYSIS
The dataflow analysis can be described as a process of
gathering information about the use, defining and dependency
of data in the analysed program [
Syntactic analysis allows for identifying control structures,
such as procedure, function or method calls, which, in their
turn, allow building call graphs, control flow graphs, and
identifying assignation and the others that allow building
dataflow graphs [
The dataflow analysis can be used for proper detection of certain types of defects (as a rule, in operation) with a minimum number of false positives: SQL-, command-, XSS-injections, other types of code injections and setting directly in the code of the authentication data. It should be noted that despite the differences in these defects, most of them implement the following defect use pattern.
1.
Data is received from the user (consequently, untrusted data).
Data propagates through the program depending on the conditions and cycles.
Data is transformed, or filtered, or remains unchanged. Finally, untrusted data gets access to the vulnerable function (buffer management, SQL query running etc.).
There is a mechanism for dataflow analysis called “taint
propagation”, which allows for identifying the defect, but also
shows the data propagation path, starting from the entry point
(user input), through the program and to the function
vulnerability [
Such code fragment can be sought using signature analysis (search as per templates). It only requires representation rule: VARIABLE (“login” OR “password”) OPERATOR (“=”) CONSTANT(*);
However, these code fragments can show that such code was written for debugging and remained in the final software version by accident, or was added intentionally, provided there was assurance that the code would not be inspected. If a malicious developer wants to hide the imbedded defect from the person, who inspects the code, but also from the means of static analysis, the code may be written, for instance, this way: String label = "somewhere".substring(0,4); String summ = LogConstant.class().getClassName().toLowerCase() ;
String upd_time = summ.substring(3, summ.lenght()-3);
Char ascii_conv = 95; String login = label + ascii_conv + upd_time; If we break down parts of code fragment into various modules and files of source texts, it will be next to impossible to identify the defect using manual analysis, as well as many known automated methods.
The “constant propagation” mechanism of the dataflow analysis may define the values of the variables, their concatenation and transfer into other variables, and final values of the variables. As a result, the defect may be identified and, consequently, unauthorized access to the functional capabilities of the software may be prevented. • Untrusted data - data received from interfaces outside the analysed code and trusted zone (allied agents, users);
Critical flow - flow from the entry point to the touch Let us define the general procedure for the search for undocumented features using dataflow analysis:
Prepare source texts and configurations of the analysed software.
Use of the static analysis tools (that implement dataflow analysis) to sourced texts and configurations prepared in step 1.
1. 2.
Dataflow analysis is divided into two stages. The first stage of analysis requires engineering of critical control and dataflows in the analysed software. Below is the sequence of the algorithm actions.
Search for the entry points of the untrusted data in the analyzed software (template-based search). This step requires a base of entry points templates formed by inspections of standard libraries and popular frameworks.
Search for the points that contain potentially vulnerable functions (template-based search as well). For each entry point of the untrusted data, add function, method and procedure calls that are happening in this point to the control flow tree.
Repeat clause 3 until you reach one of the final points specified in clause 2, or until you reach a point that does not transition into other functions, procedures or methods.
Once control flow trees are built, identify flows that have reached potentially vulnerable functions.
Consider these flows critical.
At the second stage, analyse critical control flows, their separate points (functions, procedures and methods) and identify the fact of untrusted data propagation from the entry point to the potentially vulnerable function. Below is the sequence of the algorithm actions:
Obtain entry point (function, procedure or method), engineer all dataflows that affect the data received from untrusted source.
If untrusted data after interaction with other dataflows has not changed its status, proceed to clause 3. Otherwise, complete analysis of the current critical control flow.
If untrusted data were transmitted at the following point of the critical control flow, proceed to clause 4. Otherwise, complete analysis of the current critical control flow.
If the current point is the endpoint, proceed to clause 5. Otherwise, proceed to clause 2 with a new point and new input data. Continue, until analysis of all points in the critical control flow is complete.
If the current point is the endpoint, and untrusted data were transmitted to the potentially vulnerable function from the first point, enter the critical control flow on the positive triggering list. Otherwise, finalize analysis of the current critical control flow.
The list obtained at the entry to the second stage of analysis is transferred to the entry of the report generator, which control interface is also present within the graphical user interface; after that the report generator based on the transferred list and database of the defect types draws up a report on the performed static analysis.
VI.
The following description refers to dataflow implementation in static analyzer AppChecker developed by NPO Echelon. The local analysis is normally performed for a certain block of the code (which coincides with the visibility scope depending on the programming language). The local analysis assumes obtaining information about the conditions of the program in all points of the program, i.e.:
The diagram of the local analysis algorithm can be seen in Figure 1.
You can optionally store, for instance, data on the value constancy (for the “constant propagation” tool), data assurance flag (for “taint propagation”), and information about the condition of the variable.
Information can be obtained from the local block in two opposite ways listed below:
From bottom to top: from the point susceptible to the defect make assumptions about the properties of the data transmitted into it, go up the code to the point of entry in the local area (function, procedure or method). The approach requires consideration of all options of the program run (for each branch and iteration of the cycles), which leads to “combinatorial explosion” of the information quantity, which shall be stored during analysis.
From top to bottom — from the point of entry of untrusted data into the program, down along the code, with available information about all of the above points of the program. This approach allows making assumptions about running separate branches of the program and engineer sequential analysis. The drawback of this approach is difficulty in obtaining the path from the entry point to the exit point, because the only known fact is that the path exists.
Information that is available within one function (procedure, method), as a rule, is insufficient for high quality search for the defects, because many defects propagate throughout the project, or, at least one file. Global analysis is used to link data received from different functions. The global analysis engages call graphs. To ensure operation of this analysis it is sufficient to obtain certain confirmation or assumption about the properties of input and output data of separate functions in the call graph. It is important to obtain such data in the context of the functions, which are outside of the path from the point of the data entry to the point susceptible to the defects, and which analysis is necessary because the call of such functions may change the arguments or return values, which properties may depend on the properties of the input data (for instance, the substring get function, which accepts data input by the user returns taint data, although formally it is not included in the call graph).
The diagram of the global analysis algorithm can be seen in Figure 2.
ANALYSIS
The ideal solution of the dataflow analysis task from the theoretical point of view consists in the search for all possible paths. Let us introduce certain symbols: B — data block for analysis, which consists from elementary subblocks B1, …, Bn. It is a known fact, that the dataflow values before the statement and after it are limited by the semantics of the instruction. The correlation between the dataflow values before and after the assignment statement is characterized by the transfer function. fi shall stand for a transfer function of block Bi, which characterizes transformation of data in this block. The values of the dataflow before and after subblock Bi shall be represented as IN[Bi] (OUT[Bi] accordingly).
Suppose P is a possible execution path in the flow graph:
P= Input → B1 → … → Bk.
In this case, the transfer function fP for path P will be represented by a composition of the transfer functions fk−1•…•f1. However, it should be noted that fk is not a part of the composition, which shows that the path reached the start of subblock Bk, but not its end. Let us consider that any flow graph consists of two empty subblocks - input block, which is a start point of the graph, and output block, which is passed by all exits from the graph. The transfer functions of input and output blocks are represented by constant values.
Thus, taking into account the foregoing, the ideal solution is the array:
( ) = ⋃ ( ), where is the result of the constant transfer function, which is represented by the starting input node.
It may seem that the task of the search for the ideal solution is reduced to analysis of the transfer functions fP for all paths P in the flow graph. However, it was noted by Ullmann [17, page 724], the task of the search for the ideal solution is generally unsolvable. If block B has branches, cycles and recursions, array IDEAL[B] maybe unlimited. The assistance comes from the solution of path-based gathering [17, page 757], which is similar to the path search algorithm in the graph, so called ‘breadth first search’. This algorithm allows achieving such final number of P, that an array of all fP covers all unique transformations of fB.
1. Potential SQL-injection is identified in Dolibarr project, in htdocs/admin/menus/edit.php file:
Let us write down an iterative solution to the generalized task for the dataflow. There are two versions of such algorithm - direct and reverse. The first version proceeds from input blocks to the output, the second - goes in the reverse. The basis is Ullmann’s algorithm [17, page 754].
OUT[INPUT] = ; For (each base block B, which differs from input)
OUT[B] = InitDataConst; while (changes are entered in OUT)
for (each basic block B, which differs from input) { { IN[B] = ⋃P-predecessor OUT[P] ;
OUT[B] = fB (IN[B]); } Reverse version of the algorithm: IN[INPUT] = voutput; for(each basic block B, which differs from output)
IN[B] = InitDataConst; while (changes are entered in IN) for(each basic block B, which differs from output) OUT[B] = ⋃P-predecessor B IN[P] ; IN[B] = fB (OUT[B]); }
Subject to [
It should be noted that in practice it is inadvisable to analyse all data used by the program. For example, if we consider unfiltered user input as input data vinput, we are going to be interested in B, where OUT[B] are entered in the database or output in HTML-context. Block B may also be represented by the function of the input information filtering, thus finalizing the path and marking it as safe.
IX.
EXAMPLES AND RESULTS
Dataflow analysis is widely spread in compilers and some sort of program analysis tools in order to find mistakes, typos and other accidentally inserted source code errors or weaknesses. This paper is dedicated to the implementation and usage of well-known analysis approach for detecting potentially harmful code areas deliberately inserted into source code. The paper subject novelty is in joint usage dataflow and signature template-based analysis for detection both embedded malicious code (backdoors, trapdoors, hard-code credentials) and weaknesses caused by accidental developer's mistakes.
Below are the examples of potentially harmful structures detected by the method described here using AppChecker software. These examples are real but quite simple because we think it is unacceptable to provide big and complex examples in this article.
B284 = «$sql = "SELECT m.rowid, m.mainmenu, m.level, m.langs FROM ".MAIN_DB_PREFIX."menu as m WHERE m.rowid = ".$_GET[’menuId’];» B285 = «$res = $db->query($sql);»
Data received from the user is entered in $sql variable, and the value of the variable without filtration is entered in SQLrequest, which may lead to running of random SQL code. The critical point is string B285; constant string is concatenated with taint data, and as a result the part of the string to the right of concatenation becomes taint.
2. The use of passwords set directly in the software code is identified in AWCM project, in connect.php file: B3 = «$db_hostname = "localhost";» B4 = «$db_username = "root";» B5 = «$db_userpass = "123456";» B6 = «$db_database = "awcm";» B24 = «@mysql_connect($db_hostname, $db_username, $db_userpass);»
Parameters, including the password, set directly in the code,
are used to connect to the database. The critical point is string
B24; in string B5 the right part of the expression is a constant; in
practice, the string is allocation of constant value to the variable
used further to set the password. Nowadays AppChecker, which
implements algorithms of signature analysis using flow
analysis, contains the total of 253 rules for the search of defects
in the software code in four programming languages: С/С++,
Java, PHP, C#; the rules allow identifying 113 types of defects
[
The following conclusions can came from the results of the study:
1. Based on well-reputed signature analysis approach, the suggested method of the dataflow analysis can minimize the number of false positives and simplify the development of signatures for an analyser production model.
2. The suggested method and tools will be useful for the
accredited testing laboratories as well as developers of safe
software tools. Secure software development practices (we
would, first of all, like to mention a recently approved national
standard in this field [