Oulun yliopisto - Etusivulle University of Oulu in English

ee.oulu.fi

Electrical and Information Engineering

University of Oulu > Faculty of Technology > Electrical and Information Engineering


OUSPG

[This page is CSS2 enabled. Your browser might not fully support it]

Vulnerability Analysis of Software through Syntax Testing

Rauli Kaksonen
Technical Research Centre of Finland, Electronics Institute, Networking Research
P.O.Box 1100, FIN-90571 Oulu, Finland
rauli.kaksonen@vtt.fi

Marko Laakso, Ari Takanen
University of Oulu, Department of Electrical Engineering, Computer Engineering Laboratory
Linnanmaa, PO BOX 4500, FIN-90014 University of Oulu, Finland
{fenris,art}@ee.oulu.fi

Keywords: vulnerability analysis, syntax testing, software fault injection, information security, black-box, buffer-overflow.

$RCSfile: index.html,v $ $Revision: 1.19 $ $Date: 2000/08/11 13:37:45 $

ABSTRACT

Vulnerabilities in networked software create a risk of compromise of information security. Thus, the security of networked software components should be analysed, preferably before they are deployed. This white paper presents a method of vulnerability analysis through syntax testing, and fundamental principles for an analysis tool. The introduced method focuses only on vulnerabilities and not on the correct behaviour of software, and thus reduces the required effort. The testing is done by feeding exceptional input values to the software and observing the security aspects of the resulting behaviour. The method is effective in finding faults created when implementing the software, and has many applications. Some of the vulnerabilities hidden in software components can be found without testing them for the correctness of the software. The overall effort needed is smaller than the effort required by thorough testing.

1. Introduction

Bugs persist in contemporary software and cause inconvenience and occasional loss of information. The growth of connectivity through public networks is apparent, especially in the form of the Internet. Both new and legacy systems are expected to interface with the public networks. This contributes to the risk of the vulnerabilities caused by the bugs being exploited to compromise the confidentiality, integrity and availability of information.

Security is one of the aspects of software quality. Quality is evaluated by software testing to reduce faults in released software. Traditionally, software testing attempts to ensure that the software meets the specifications rather than trying to find vulnerabilities in software [Beizer]. Vulnerability analysis is classically reactive, addressing vulnerabilities from released software products based on publicly disclosed vulnerabilities [Laakso]. There have been, and are, attempts to move towards a more proactive approach, eliminating vulnerabilities before software is deployed [McGraw] [Ghosh] [Miller] [Griffin] [PROTOS].

Vulnerabilities contribute to the security risk related to the use of software. Trivial vulnerabilities are constantly disclosed in the public mailing-lists [Bugtraq]. One significant type of software vulnerability is buffer overflow [Ghosh1]. A buffer overflow is caused when an input buffer in memory runs out, due to missing bound checking. Malicious code can be executed on a remote system by carefully designing a sequence of bytes to overwrite the program space after the buffer. Many of the discovered vulnerabilities are buffer overflows, which makes them deadly serious from the system security point of view.

It seems that the software testing exercised by the developers of software components does not reliably catch vulnerabilities. On the other hand, the disclosure and fixing of vulnerabilities in shipped products is expensive and inconvenient [McGraw]. The gap between the mature discipline of software testing and ad-hoc vulnerability analysis must be addressed.

This paper introduces a systematic approach of vulnerability testing, a method which combines software testing and vulnerability analysis. First, we present some background techniques used in our approach: syntax testing, software fault injection and penetration testing. Then we describe vulnerability analysis through syntax testing, and provide a follow-up discussion.

2. Testing Techniques

2.1. Syntax Testing

In syntax testing, the test-cases, i.e. the input to the software, are created based on the specifications of languages understood by the interfaces of a software [Beizer]. Interfaces have many formats: command-line prompts, files, environment variables, pipes, sockets, etc. An interface has a language which defines what is legal input to the interface and what is not. This language may be hidden or open. The existence of a hidden language is not explicitly realised by developers of the software, but a piece of software might nevertheless read some input data, parse it, and act accordingly. In a broader sense, hidden languages exist also in data structures used to transfer information from a software module to another. An open language is appropriately specified in the software documentation.

The motivation for syntax testing springs from the fact that each interface has a language, whether it is hidden or open, from which effective tests can be created with a relatively small effort. Syntax testing is more likely to find faults from the portions of software responsible for hidden language handling, because open languages must have been explicitly considered by the programmer and thus the input handling portion is likely to be better.

Automated syntax testing requires a formal description of the input language in machine readable format. If the language is hidden, the tester must create a specification for it. Common choices are BNF (Backus-Naur form) and regular expressions. Both are notations to define context-free grammar languages. A sentence is a sequence of bytes which are arranged according to the rules of the language. Context-free languages have traditionally been used in compilers of various sorts to create parsers for input sentences. In syntax testing, a context-free language is the base used to generate sentences. These sentences are then fed, or injected, into the software being tested to see if it accepts them, rejects them or fails to process them altogether.

The selection of test-cases in syntax testing could start with single-error sentences. This is likely to reveal most faults assuming the faults are mutually independent and a fault is triggered by one error in a sentence. After all the sentences with one error are tried, the testing proceeds to pairs of errors, three error combinations, and so on. The number of test-cases grows exponentially by the number of combined errors. Several different kinds of errors can be produced in syntax testing: [Beizer]

Syntax errors
Syntax errors violate the grammar of the underlying language. They are created by removing an element, adding an extra element and providing the elements in wrong order. Syntax errors can exist on different levels in the grammar hierarchy: top-level, intermediate-level and field-level.
Delimiter errors
Delimiters mark the separation of fields in a sentence. In ASCII-coded languages the fields are normally characters and letters, and delimiter are white space characters (space, tab, line-feed, etc.), or other delimiters characters (commas, semicolons, etc.) or their combinations. Delimiters can be omitted, multiplied or replaced by other unusual characters. Paired delimiters, such as braces, can be left unbalanced.
Field-value errors
A field-value error is an illegal field in a sentence. Normally, a field value has a range or many disjoint ranges of allowable values. Field errors can include values which are one-below, one-above and totally out-of-range. Values exactly at the range boundary should also be checked.
Context-dependent errors
A context-dependent error violates some property of a sentence which cannot, in practise, be described by context-free grammar.
State dependency error
Not all sentences are acceptable in every possible state of a software component. A state dependency error is generated by inputting a correct sentence during an incorrect state.

Automatic generation of sentences leads to automatic test design where test-cases are designed by a computer. It is suitable, for example, for stress testing, where software is fed with a large amount of input data [Beizer].

2.2. Software Fault Injection

Fault injection techniques are traditionally applied to hardware testing, where parts of the hardware are purposefully damaged to test the robustness of the whole system. In software fault injection code or software input is modified and the resulting behaviour of the software is monitored [Voas]. Software fault injection gives information about how the software is likely to behave under exceptional conditions, i.e. how robust the software is.

Fault injection by source code modifications cannot be applied in a black-box manner. Fault injection by input modifications resembles stress testing by harsh input values or syntax testing with garbage input. In addition, the proposed testing method consists of input modifications into the software, but not into the internal interfaces.

2.3. Penetration Testing

Penetration testing is a search for vulnerabilities from software or a computer system. Penetration testing is normally done by a specialised team of experts called a tiger team [McGraw]. When a vulnerability is found and exploited, the system is said to be penetrated.

During penetration testing, the tester can scan for vulnerabilities which have been found earlier from similar systems. This testing is based heavily on the experience of the tester. The search for known vulnerabilities can be manual, but there also are tools for it [Voas]. These tools are often referenced as security scanners. Security scanners are based on a databases containing known vulnerabilities.

Penetration testing can also be based on the systematic creation of malicious input data fed to a tested software component. There are automated tools for this kind of penetration testing [Ghosh2] [Miller] [Griffin]. This is also our approach, which is described in detail in the following chapters.

3. Vulnerability Analysis through Syntax Testing

Based on the presented software testing techniques, we introduce an approach for vulnerability analysis through syntax testing. In this paper, we use the term vulnerability testing for our testing approach. In vulnerability testing, the security aspect of a software component is evaluated by injecting malicious input into it. The input creation methods of syntax testing are used. Vulnerability testing is a black-box testing method, and can thus be used to evaluate the robustness of both the deployed software and the software components under development. Vulnerability testing has the following phases:

  1. Round-up of interfaces, which the software uses to get input, especially interfaces to external systems.
  2. Specification of protocols used by the tested interfaces. One specification will do if multiple products implementing the same protocol are being tested.
  3. Execution of tests.
  4. Inspection and verification of test results.

A test is divided to test-cases. A test-case is made up of the selected input data fed to the software and the monitored software behaviour. An essential feature, derived from syntax testing, is that a test-case is failed if any behaviour that indicates the possible existence of a vulnerability is detected. Otherwise the test-case is passed. This is quite different from the testing for correctness, where a test-case is passed if the software behaved correctly and failed on other cases.

The round-up of the external interfaces of the software should identify all interfaces which can be used to exploit vulnerabilities lurking in the software. The most interesting interfaces are those open for external inspection, for example, network connection. A system often contains surprising interfaces which are potentially accessible from outside of the system. A software component accesses interfaces through library calls which may also be vulnerable. Protocols define and specify the communication between interfaces. The most obvious place for a vulnerability is in the part of the software responsible for protocol interpretation.

Every protocol has a language that states how characters or bytes are exchanged between interfaces. A protocol must also have, in order for the protocol to achieve something, a meaning. The information carried by each packet of the protocol must be specified. The meaning cannot be captured by context-free languages and must be specified by text, pictures, etc. in the protocol specification. As vulnerability testing uses context-free languages for protocol input generation, in an ideal case the meaning can be ignored.

Vulnerability testing focuses on vulnerabilities. This focus affects the selection of input fed to the software, as well as the monitoring of the tested software component. Inputs should be selected so that the likelihood of the tests revealing the vulnerabilities is maximised. This requires understanding the reasons and mechanisms which lead to information security vulnerabilities. The monitoring should be capable of recognising vulnerable behaviour, such as a software crash endangering integrity, and the availability of information. The instrumentation responsible for the monitoring must be placed between the tested software and the operating system, because failures caused by vulnerabilities often manifest themselves by system calls and signals.

Vulnerability testing has same limitations as syntax testing:

  • The tested software may behave completely inappropriately according to specifications, even if it has passed all tests.
  • Vulnerability testing is only likely to reveal errors in software implementation, as specification and design errors require complex test-cases with a specific sequence of events and conditions.
  • Not everything can be monitored (this applies to all software testing). The ways to compromise security are unlimited whereas we can only monitor limited aspects of behaviour.

4. Discussion

Our prototype has been used to find vulnerabilities in software products. While vulnerabilities of this kind have been and still are found and disclosed on a daily basis, this process has typically been more or less non-systematic. We did our tests in a predictable and repeatable manner: test-sets and schedules were planned beforehand and all executed test-sets and results were logged.

The subjects have been analysed for specific types of vulnerabilities, not for correctness. Correctness analysis would have required specifying both input and output of the subject for each test-case. This work can be laborious and difficult to do automatically. Further, in the case of a black-box subject, it would have required information which is not specified anywhere, except possibly in the proprietary documents of developers. On the other hand, the proposed approach has found vulnerabilities in several software implementations. This implies that vulnerability testing might be conducted with less effort and information than testing for correctness. In general, vulnerability testing can be used by parties who do not have the resources or knowledge to test a software component for correctness.

There are several scenarios for such testing:

  • Development-time testing; vulnerability testing is used as a complementary testing technique with other testing techniques.
  • Acceptance testing; a software component must pass a set of vulnerability tests as part of acceptance testing.
  • Buy-decision support; the purchaser of software component uses vulnerability testing to gain more data to base buying decisions on.
  • Tiger-team testing; an independent tiger-team uses vulnerability testing to asses the security of software components.

Vulnerability testing has some notable limitations. No vulnerabilities are likely to be found if the developers of the software components did a good and professional job. Well-established unit testing should catch implementation faults. A wide use of the vulnerability tool is also likely to cause a pesticide-paradox: a software product which is tested will become immune to it [Beizer]. Tests no longer reveal vulnerabilities because the same tests have been executed earlier and faults found by them have been already fixed. While we are planning to make the test-tool more sophisticated and likely to expose more subtle vulnerabilities, there always are many vulnerabilities not discovered by it. In this sense, we can only draw a baseline by testing products with a vulnerability testing tool and state whether they are below or above it:

  • Products below the baseline are insecure.
  • Products above the baseline do not contain the (trivial) vulnerabilities searched by the test-tool.

The real benefit for large-scale testing using a vulnerability test-tool would be that networked software have a smaller number of trivial vulnerabilities. With this kind of testing, it is possible to prevent the re-introduction of such faults from the reuse of legacy code, or re-introduction by programmers who are not aware of the past problems. This would cut down the number of security patches released by software producers. If less patches are released, they are more likely to be installed by system administrators and home users. A casual hacker would have more difficulties in finding vulnerabilities if the trivial ones are caught in the testing phase of the development.

5. Conclusions

This paper has introduced a proactive testing method for vulnerability analysis by vulnerability testing. The purpose of vulnerability testing is to analyse the existence of implementation level vulnerabilities in software components. This method of testing can be applied to an external piece of software without additional information or help from the developers.

The presented method of vulnerability testing is a combination of syntax testing and fault injection techniques. It is done in a black-box manner based solely on the specifications of the communication protocols used by the software. The piece of software is not tested for correctness of operation, but for vulnerable behaviour patterns. Without knowing the internal operations of the software and without reverse engineering the software, the method provides an effective way of evaluating the security aspects of software products. It is an addition to traditional testing. With little effort, it provides the means for several developers to perform a limited evaluation against the existence of traditional and well-known security faults such as buffer overflows.

The vulnerabilities found with the presented method are limited to faults made during software implementation. This is because the tool only considers individual inputs to the tested software, ignoring the larger scale vulnerabilities and vulnerable conditions which design, specification and configuration errors may cause. Implementation errors can also produce vulnerable behaviour not caught by vulnerability testing, as there is an infinite number of ways for creating insecure code and it is impossible to test against all of them.

A wide use of automated vulnerability testing could increase the security of public networks by eliminating trivial vulnerabilities. By testing the trivial vulnerabilities before shipment the need of patches would be reduced, which could make it more likely that they are installed. Further, a casual hacker looking for vulnerabilities would not find them as easily. The vulnerability analysis could be done both by developers of software components and by independent tiger-teams. Because it requires less effort than testing for correctness it is feasible also when there is not enough time or information for throughout testing.

References

[Beizer]
Beizer B. (1990) Software Testing Techniques, Second Edition, ISBN 0-442-20672-0.
[Bugtraq]
Bugtraq mailing list <http://www.securityfocus.com/> (Accessed 2000-08-10).
[Ghosh1]
Ghosh, A. and O'Connor, T. (1998) Analyzing Programs for Vulnerability to Buffer Overrun Attacks. 21st National Information Systems Security Conference, October 6-9, 1998, Crystal City, VA.
[Ghosh2]
Ghosh A. K., Schmid M., Shah V. (1998) Testing the Robustness of Windows NT Software. Symposium on Software Reliability Engineering (ISSRE'98), November 4-7, 1998, Paderborn, GE.
[Griffin]
Griffin J. L. (1999) Testing Protocol Implementation Robustness. 29th Annual International Symposium on Fault-Tolerant Computing, June 1998, Madisonn, Wisconson.
[Laakso]
Laakso M., Takanen A., Röning J.(1999) The Vulnerability Process: a tiger team approach to resolving vulnerability cases. In proceedings of the 11th FIRST Conference on Computer Security Incident Handling and Response, Brisbane. 13-18 June, 1999.
[Marick]
Marick B. (1995) The Craft of Software Testing, Prentice Hall, ISBN 0-13-177411-5.
[McGraw]
McGraw G. (1998) Testing for Security During Development: Why we should scrap penetrate-and-patch. IEEE Aerospace and Electronic Systems, April 1998.
[Miller]
Miller B. P., et. al. (1995) Fuzz Revisited: A Re-examination of the Reliability of UNIX Utilities and Services. Networked Computer Science Technical Reports Library CS-TR-95-1268, UW Madison Computer Sciences Department, April 1995
[PROTOS]
PROTOS. (1998) Security Testing of Protocol Implementations. Project homepages available at: <http://www.vtt.fi/ele/research/net/projects/protos.htm> and <http://www.ee.oulu.fi/research/ouspg/protos> (Accessed 2000-08-10).
[Voas]
Voas M. J., McGraw G. (1998) Software Fault Injection, John Wiley & Sons, Inc., 1998, ISBN 0-471-18381-4.

[This page is CSS2 enabled. Your browser might not fully support it]