111111
`
`1111111111111111111111111111111111111111111111111111111111111
`US007284274Bl
`
`c12) United States Patent
`Walls et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,284,274 Bl
`Oct. 16, 2007
`
`(54) SYSTEM AND METHOD FOR IDENTIFYING
`AND ELIMINATING VULNERABILITIES IN
`COMPUTER SOFTWARE APPLICATIONS
`
`(75)
`
`Inventors: Thomas J. Walls, East Setauket, NY
`(US); Viren Shah, Ashburn, VA (US);
`Anup K. Ghosh, Centreville, VA (US)
`
`(73) Assignee: Cigital, Inc., Dulles, VA (US)
`
`( *) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 682 days.
`
`(21) Appl. No.: 10/050,764
`
`(22)
`
`Filed:
`
`Jan. 18, 2002
`
`Related U.S. Application Data
`
`(60)
`
`Provisional application No. 60/262,085, filed on Jan.
`18, 2001.
`
`(51)
`
`Int. Cl.
`(2006.01)
`G06F 15118
`(52) U.S. Cl. ........................................... 726/25; 726/22
`(58) Field of Classification Search ................ 713/201;
`726/25
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,924,408 A *
`4,941,102 A *
`5,132,972 A *
`5,133,045 A *
`5,247,693 A *
`5,293,629 A *
`5,500,941 A *
`5,581,696 A *
`5,699,507 A *
`5,761,408 A *
`
`511990 Highland . ... .. ... ... ... ... .. . 706160
`7 I 1990 Darnell et a!. ................ 706160
`711992 Hansen ........................ 714138
`7 I 1992 Gaither et a!. ................ 706146
`911993 Bristol
`....................... 7171139
`311994 Conley eta!. .............. 7171154
`311996 Gil .............................. 714138
`1211996 Kolawa et al ................ 714138
`1211997 Goodnow eta!. ............ 714138
`611998 Kolawa et al ................ 714138
`
`5,784,553 A *
`5,842,019 A *
`5,850,516 A *
`5,854,924 A *
`5,860,011 A *
`5,922,079 A *
`5,925,123 A *
`5,970,242 A *
`6,014,723 A *
`6,085,029 A *
`6,125,439 A *
`6,148,401 A *
`6,154,876 A *
`6,381,698 B1 *
`
`711998 Kolawa et al ................ 714138
`. ............ 7171130
`1111998 Kolawa et al.
`1211998 Schneier ...................... 726125
`1211998 Rickel et a!.
`............... 7171132
`111999 Kolawa et al .............. 7171142
`711999 Booth eta!. .................. 714126
`711999 Tremblay eta!. ........... 7121212
`1011999 O'Connor eta!. .......... 7171100
`112000 Tremblay eta!. .............. 71111
`712000 Kolawa et al ................ 714138
`912000 Tremblay et a!. ........... 7121202
`1112000 Devanbu et a!. ............ 7131170
`1112000 Haley et al ................. 7171133
`412002 Devanbu et a!. ............ 7131170
`
`(Continued)
`
`OTHER PUBLICATIONS
`
`D. Wagner, J. Foster, E. Brewer, and A. Aiken. A first step towards
`automated detection of buffer overrun vulnerabilities. In Network
`and Distributed System Security Symposium, San Diego, CA, Feb.
`2000.*
`
`(Continued)
`
`Primary Examiner-Nasser Moazzami
`Assistant Examiner-David Garcia Cervetti
`(74) Attorney, Agent, or Firm-Edell, Shapiro & Finnan,
`LLC
`
`(57)
`
`ABSTRACT
`
`A system and method for certifYing software for essential
`and security-critical systems. The system and method pro(cid:173)
`vide a methodology and corresponding analysis engines
`increase the level of confidence that common vulnerabilities
`are not present in a particular application. A pipeline system
`consisting of independent modules which involve increas(cid:173)
`ingly complex analysis is disclosed. The pipeline approach
`allows the user to reduce computation time by focusing
`resources on only those code segments which were not
`eliminated previously in the pipeline.
`
`11 Claims, 2 Drawing Sheets
`
`PREPROCESSOR/
`PARSER
`
`200
`.!
`
`PREPROCESSED
`CODE&AST
`
`206
`'-\
`
`202
`
`...JSTAGE 1:
`204 VulCAn
`
`STAGE II:
`STATIC
`AN~YSIS
`208
`
`STAGE Ill:
`DYNAMIC
`AN~YSIS
`210
`
`KNOWLEDGE
`DATABASE
`
`Blue Coat Systems - Exhibit 1005 Page 1
`
`

`
`US 7,284,274 Bl
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`6,412,071 Bl *
`6,427,232 Bl *
`6,473,896 Bl *
`6,513,154 Bl *
`6,578,094 Bl *
`6,584,569 B2 *
`6,718,485 Bl *
`6,806,893 Bl *
`6,807,569 Bl *
`6,862,696 Bl *
`6,895,578 Bl *
`200110013094 AI*
`2002/0026591 Al *
`2003/0233581 Al *
`2004/0006704 Al *
`2004/0103315 Al *
`
`6/2002 Hollander et a!.
`............ 726/23
`7/2002 Ku eta!. .................... 717/124
`10/2002 Hicken eta!. .............. 717/132
`112003 Porterfield .................. 717/101
`6/2003 Moudgill ..................... 710/57
`6/2003 Reshef et al .................. 726/25
`4/2004 Reiser ......................... 714/38
`10/2004 Kolawa et al .............. 715/848
`10/2004 Bhimani eta!. ............ 709/217
`3/2005 Voas eta!. .................... 714/38
`5/2005 Kolawa et al.
`. ............ 717/130
`8/2001 Etoh et a!. .................. 712/227
`212002 Hartley et a!. .............. 713/201
`12/2003 Reshef et al ................ 713/201
`112004 Dahlstrom et al.
`. ........ 713/200
`5/2004 Cooper et a!. .............. 713/201
`
`OTHER PUBLICATIONS
`
`Necula et al., The design and implementation of a certifYing
`compiler, 1998, ACM, pp. 333-344.*
`Bush et a!., A static analyzer for finding dynamic programming
`errors, 2000, Software Practice and Experience, pp. 775-802.*
`
`Viega, J.; Bloch, J.T.; Kohno, Y.; McGraw, G., ITS4: a static
`vulnerability scanner for C and C++ code, Dec. 2000, IEEE, pp.
`257-267.*
`D. Wagner, J. Foster, E. Brewer, and A. Aiken. A first step towards
`automated detection of buffer overrun vulnerabilities. In Network
`and Distributed System Security Symposium, San Diego, CA, Feb.
`2000.*
`Necula et al., The design and implementation of a certifYing
`compiler, 1998, ACM, pp. 333-344.*
`Bush et a!., A static analyzer for finding dynamic programming
`errors, 2000, Software Practice and Experience, pp. 775-802.*
`Viega, J.; Bloch, J.T.; Kohno, Y.; McGraw, G., ITS4: a static
`vulnerability scanner for C and C++ code, Dec. 2000, IEEE, pp.
`257-267.*
`Ghosh et a!., An Approach for CertifYing Security in Software
`Components, 1998, Proc. 21st {NIST}-{NCSC} National Informa(cid:173)
`tion Systems Security Conference, <citeseer.ist.psu.edu/104720.
`htrnl>.*
`Ghosh, A.K.; O'Connor, T.; McGraw, G., An automated approach
`for identifYing potential vulnerabilities in software, 1998, Security
`and Privacy, 1998. Proceedings. 1998 IEEE Symposium on, May
`3-6, 1998 pp. 104-114.*
`* cited by examiner
`
`Blue Coat Systems - Exhibit 1005 Page 2
`
`

`
`U.S. Patent
`
`Oct. 16, 2007
`
`Sheet 1 of 2
`
`US 7,284,274 Bl
`
`10
`/
`
`void OVERFLOW ( char *pointer) {
`
`char SMALL [100];
`
`strcpy SMALL, pointer);
`
`}
`
`void MAIN() {
`char LARGE [2000];
`int i;
`
`for (i=O ; i<2000 ; i++)
`LARGE [i] = 'x' ;
`overflow (LARGE);
`
`}
`
`FIG. 1A
`
`SMALL ---._/14
`
`D
`
`FIG.1C
`
`LARGE ----12
`
`X
`X
`X
`X
`
`X
`X
`X
`
`FIG. 1B
`
`SMALL
`
`__._/ 22 '--
`
`PROGRAM ~20~ PROGRAM
`STACK
`STACK
`X
`...
`X
`X
`...
`X
`
`SFP
`
`RET I P
`
`.--/ 26 '---
`
`*POINTER
`
`X
`...
`X
`
`X
`...
`X
`
`FIG. 10
`
`Blue Coat Systems - Exhibit 1005 Page 3
`
`

`
`U.S. Patent
`
`Oct. 16, 2007
`
`Sheet 2 of 2
`
`US 7,284,274 Bl
`
`PREPROCESSOR/
`PARSER
`
`200
`J
`
`PREPROCESSED
`CODE &AST
`
`206
`'-\
`
`202
`
`AST
`
`E---3 ~
`1---+~11
`E---3
`
`,_;STAGE 1:
`204 VulCAn
`
`KNOWLEDGE
`DATABASE
`
`FIG. 2
`
`STAGE II:
`STATIC
`AN~YSIS
`208
`
`STAGE Ill:
`DYNAMIC
`AN~YSIS
`210
`
`300
`.!
`
`1500
`
`1000
`
`500
`
`0
`
`GREP
`
`STAGE I STAGE II
`VULCAN STATIC
`ANALYSIS
`
`MINUTES
`
`3
`
`4
`
`900
`
`FIG. 3
`
`STAGE Ill
`DYNAMIC
`ANALYSIS
`(PROJECTED)
`1500
`
`Blue Coat Systems - Exhibit 1005 Page 4
`
`

`
`US 7,284,274 Bl
`
`1
`SYSTEM AND METHOD FOR IDENTIFYING
`AND ELIMINATING VULNERABILITIES IN
`COMPUTER SOFTWARE APPLICATIONS
`
`2
`under any conditions, including normal operation, as well as
`unusual or attack conditions, can result in immediate loss of
`revenue, as well as jeopardizing the long-term viability of
`the business. For instance, well-known flaws in CGI scripts
`have enabled hackers to alter Web pages with political
`messages. If the Web pages of a financial investment firm
`were vandalized, investors and Wall Street would likely lose
`confidence in the ability of the firm to securely manage the
`assets of firm's investors.
`For companies that develop and release application soft-
`ware, the expense in adequately addressing security vulner(cid:173)
`abilities is very high. Moreover, for any vulnerabilities that
`were not adequately foreseen, there will be a corresponding
`drop in consumer confidence which carmot be measured. For
`15 example, both Netscape and Microsoft experienced well(cid:173)
`publicized security-related flaws in their Internet browsers in
`1997.
`Developers of operating systems such as Sun Microsys(cid:173)
`tems and Hewlett-Packard also spend considerable human
`resources tracking bugs that have the potential to be security
`flaws in their commercial operating systems. Such costs are
`often transferred to the end users, either directly (in the form
`of increased software prices) and indirectly (in the form of
`increased maintenance costs). It is well-known that the time
`and expense involved for system administrators to patch,
`upgrade, and maintain the security of computer systems is
`very high and increases with both new software additions
`and more sophisticated attacks.
`The buffer overrun attack is one of the most pervasive
`30 modes of attack against computer systems today. Probably
`the most infamous buffer overrun attack is the Morris worm
`of 1988 that resulted in the shutdown of a significant portion
`of the Internet infrastructure at the time (which consisted of
`primarily university and goverument nodes). The worm was
`35 a self-propagating buffer overrun attack that exploited a
`program vulnerability in the Unix fingerd network service.
`The worm illustrated the serious nature of software flaws
`and how they can be leveraged to breach security on other
`systems.
`Since the Morris worm, buffer overrun attacks have
`become a very popular method of breaking into systems or
`obtaining super user privilege from user-level accounts.
`According to statistics released by the Computer Emergency
`Response Team (CERT) Coordination Center of Carnegie
`Mellon University's Software Engineering Institute, about
`50 percent of computer incidents reported today in the field
`involve some form of buffer overrun.
`To further complicate the problems presented with appli(cid:173)
`cation software, unsafe languages, such as C, make buffer
`50 overflow attacks possible by including standard functions,
`such as, for example, gets, strcat, and strcpy, that do not
`check the length of the buffer into which input is being
`copied. If the length of the input is greater than the length of
`the buffer into which it is being copied, then a buffer
`55 overflow can result. Safe progrming practices that allow
`only constrained input can prevent a vast majority of buffer
`overflow attacks. However, many security-critical programs
`already in the field today do not employ safe programming
`practices. In addition, many of these programs are still coded
`60 in commercial software development labs in unsafe lan(cid:173)
`guages today.
`As described above, buffer overrun attacks are made
`possible by program code that does not properly check the
`size of input data. When input is read into a buffer and the
`length of the input is not limited to the length of the buffer
`allocated in memory, it is possible to run past the buffer into
`critical portions of the stack frame. Overrunning the buffer
`
`65
`
`This application claims the benefit of U.S. Provisional
`Application No. 60/262,085, filed Jan. 18, 2001, which is
`herein incorporated by reference in its entirety.
`This invention was made with Govermnent support under
`Cooperative Agreement No. 70NANB7H3049 administered
`by the National Institute for Standards and Technology. The 10
`Govermnent has certain rights in the invention.
`
`BACKGROUND
`
`1. Field of the Invention
`The present invention relates generally to computer sys(cid:173)
`tem security, integrity, and reliability. More particularly, the
`present invention relates to examination and certification of
`software application programs to identifY and eliminate
`vulnerabilities arising from poor software application pro- 20
`grarmning techniques.
`2. Background of the Invention
`The explosion of electronic cormnerce has placed com(cid:173)
`puter software applications at the cornerstone position of
`on-line business. Software is the brick and mortar of the new 25
`economy, but the migration from physical to virtual retail
`space has placed both the consumer and vendor at risk in
`unforeseen ways. If the new economy is going to survive,
`software will have to become more resistant to attack and
`will have to continuously improve to meet the rigorous
`demands of an on-line market.
`An example of the magnitude of the problems faced by
`software users is illustrated by the distributed denial-of(cid:173)
`service (dDoS) attacks against major e-cormnerce sites of
`February, 2000. Some of the brightest luminaries in e-com(cid:173)
`merce, including Yahoo!, Amazon.com, Buy.com, ZDNet,
`and CNN.com were effectively taken down for a period of
`hours by these attacks. What is most impressive and dis(cid:173)
`turbing about these attacks is that they were against very
`high volume sites. For instance, according to Media Metrix, 40
`an online traffic measurement firm, Yahoo! had more unique
`visitors in January 2000 than any other online site. The other
`victims were among the top fifty sites. The dDoS attacks
`were able to bombard these sites with data at rates of up to
`one gigabit of data per second. The collective downtime of 45
`these sites resulted in a loss of revenue estimated to be in the
`millions of U.S. dollars.
`Though denial-of-service (DoS) attacks often exploit
`weaknesses in protocols to hold network services hostage to
`the attacks, what is often overlooked by analysts is that such
`dDoS attacks are often made possible by flaws in software.
`A key to implementing an effective dDoS attack is to
`compromise a very large number of machines in order to
`plant the dDoS attack software, which, in the February
`attacks, went by names such as Trinoo or TFN2000. Sites are
`usually compromised in the first place by exploiting some
`flaw in software. In the case of many dDoS attacks, Unix
`servers are compromised, often by a well-known flaw in the
`Remote Procedure Call (RPC) service. Once a site is com(cid:173)
`promised and the malicious software installed, the compro(cid:173)
`mised site becomes a zombie that acts maliciously on
`command at some future time. One of the keys to preventing
`these types of attacks in the future is to secure the software
`on the server systems such that they are not vulnerable to
`compromise in the first place.
`In any e-commerce site, the software that runs the site is
`business-critical by definition. The failure of the software
`
`Blue Coat Systems - Exhibit 1005 Page 5
`
`

`
`US 7,284,274 Bl
`
`3
`results in writing to memory that is not reserved exclusively
`for the buffer. The consequences of overrunning a buffer can
`range from no discernible effect to failure of the program
`execution, and even to execution of machine instructions
`contained in the input. If the unconstrained input can write
`over specific data in the program stack frame, then it may be
`possible to execute arbitrary program code included in the
`input.
`The stack frame is the part of a process' address space that
`is used to keep track of local function data when a function
`is called. When calling a function, a new stack frame is
`created for the function that is called. The calling function
`"pushes" the address of the next instruction to be executed
`after returning from the called function on this stack. This
`address is known as the return instruction pointer. After the
`program finishes executing the called function, a pointer to
`the next instruction to be executed is "popped off' the stack.
`The value of the operation code ( opeode) pointed to by the
`instruction pointer is loaded and that instruction is executed.
`By overwriting a buffer allocated on the stack, it is 20
`possible to change the instruction pointer to point to another
`address. In the case of many program crashes caused by
`buffer overruns, the instruction pointer is overwritten with
`random or garbage data that does not correspond to a
`legitimate instruction address. Upon returning from the 25
`called function, the processor attempts to execute an invalid
`instruction and an exception is generated. In this case, the
`program will normally abort execution, usually (but not
`always) without serious consequence on security, safety or
`integrity.
`On the other hand, if the input stream that overruns the
`buffer is carefully crafted, it is possible that the instruction
`pointer can be overwritten in a principled manner. That is, a
`specific address can be written into the instruction pointer so
`that when it is evaluated, the next instruction to be executed 35
`is located at an address in the stack frame. With the address
`pointing back into the stack, it is possible to execute any
`instructions embedded in the input stream that have been
`written into the stack.
`The process to implement the buffer overrnn is commonly
`known as "smashing the stack." An exemplary process for
`smashing the stack or overrunning buffers is illustrated in
`FIGS. lA and lB. Program 10 includes the function
`"MAIN" which defines array variable 12 (illustrated in FIG.
`lB) with the label "LARGE." Array LARGE is defined with
`a length of two thousand bytes. After creating the array
`LARGE, function MAIN fills it with two thousands "X"
`characters, as shown in FIG. lB. Next, function MAIN calls
`the function "OVERFLOW" with a pointer to array
`"LARGE" passed as an argument. In OVERFLOW, array
`variable 14, labeled "SMALL," is defined with a length of
`one hundred bytes (illustrated in FIG. lC). The left side of
`FIG. lD shows program stack 20 illustrating how memory
`is allocated when the OVERFLOW function is called in
`program 10. As shown in FIG. lD, the array SMALL is
`allocated one hundred bytes, represented by block 22. After
`SMALL, program stack 20 has memory reserved for the
`stack frame pointer (SFP) in block 24, the return instruction
`pointer (IP) in block 26, and the pointer (in block 28) that
`was pushed onto the stack when OVERFLOW was called.
`After creating array SMALL, the OVERFLOW function
`simply copies the contents of the array LARGE into the
`memory reserved for array SMALL using C's strcpy func(cid:173)
`tion.
`Unfortunately, strcpy does not check the length of the
`source variable before copying it to the destination variable.
`As a result, the two thousand "X" characters are written into
`
`4
`the one hundred character long array (block 22) and into the
`adjoining memory locations as shown in the right side of
`FIG. lD. That is, after the first one hundred Xs are copied,
`the remaining nineteen hundred characters will overwrite the
`SFP, the return IP, and even the pointer.
`After the OVERFLOW function finishes executing, the
`processor will pop off the return IP address and execute the
`instruction located at that address. In this example, the
`address pointed to by the integer value of X ... X (length
`10 of pointer will depend on the system architecture) is prob(cid:173)
`ably not an instruction, and as a result, program 10 will
`probably crash. However array LARGE could have been
`intelligently loaded with input that places a meaningful
`address at the return IP location. After returning from the
`15 OVERFLOW function, the next instruction that will execute
`will be whatever instruction is stored in the address stored in
`the return IP location. If the attacker inserts instructions (i.e.
`code) into another location within the overrnn buffer (i.e.,
`boxes 22-28 or beyond), then the attacker could also insure
`the return IP location (box 226) then points to the location
`of his code and will be able to execute code of his own
`choice.
`This technique is as effective as being able to access and
`modifY the program source code, recompile it, and execute
`it without ever having access to the local source code.
`Smashing the stack is one of the primary attacks launched
`against SUID root programs, i.e., programs that run as the
`super user on UNIX-based systems. The problem illustrated
`in FIGS. lA-lD was that a progrannning error allowed a
`30 large buffer to overwrite a smaller buffer. In the Figure it
`may seem fairly apparent that this would happen, but in
`many programs, the programmer is assuming that the user
`will input values well within the buffers allocated. However,
`no provision is made to handle input from a malicious or
`even careless user. The exploit was made possible in this
`case because the progrannner used the strcpy function
`instead of some other function that would have performed
`bounds checking to prevent the data from being overwritten.
`In the wake of many well-publicized online failures, such
`40 as those described herein, as well as failures of online
`trading firms to meet customer demands at critical times, one
`or more government agencies or other self-governing bodies
`may well institute new requirements on public firms whose
`financial health depends on their information technology
`45 (IT) systems. For example, regulatory bodies, such as the
`U.S. Securities and Exchange Commission (SEC), could
`require publicly-traded companies to issue audited state(cid:173)
`ments on the ability of their IT systems to withstand unusual
`conditions, such as volatile market conditions, high con-
`50 sumer demand, as well as malicious attack.
`Software certification is the process of analyzing software
`to determine whether or not the risks posed by the software
`are acceptable for a business critical environment. It is an
`assessment process that is acceptable in a business paradigm
`55 where software vendors can obtain independent, third party
`assurance that the vendor's software is reliable, safe, or
`secure in a given application.
`To date, certification is largely performed on people and
`processes. Thus, a particular organization may be certified to
`60 produce commercial grade software by meeting an industry
`accepted standard for process maturity, such as the Software
`Engineering Institute's Capability Maturity Model (SEI(cid:173)
`CMM) or International Standards Organization (ISO) 9000
`standards. Similarly, individuals may be certified to work on
`65 particular hardware and software platforms. Examples are
`obtaining the Microsoft Certified Systems Engineer (MCSE)
`certification or obtaining Professional Engineer (PE) certi-
`
`Blue Coat Systems - Exhibit 1005 Page 6
`
`

`
`US 7,284,274 Bl
`
`6
`that are potentially dangerous. ITS4 is not sufficient for
`identifying potential vulnerabilities because it is not context(cid:173)
`or flow-sensitive and thus it is not possible for it to reduce
`the large number of potential vulnerability locations it
`identifies.
`Another approach has been examined in the recent work
`in the static detection of buffer overflow vulnerabilities by
`David Wagner eta!. of University of California, Berkeley.
`Wagner attempts to place provably maximal hounds on the
`properties of the arguments passed to library calls. Then,
`using that information one can determine whether or not
`certain heuristic policies have be violated. In the case of
`buffer overflows, Wagner reduces strings to be represented
`by two variables; all other information is abstracted away.
`This simple string representation allows an analyst to only
`focus on the string properties most important in detecting
`buffer overrun problems. The constraint language developed
`by Wagner is very powerful, but the scarming techniques
`taken in his approach are overly simplified and still lead to
`a large number of false positives.
`Accordingly, a need therefore exists for systems and
`methods for providing certification for any essential soft(cid:173)
`ware system, where the failure of that software may result in
`unacceptable losses, financial or otherwise.
`
`SUMMARY OF THE INVENTION
`
`5
`fication in a particular State to practice engineering. These
`certification processes are designed to encourage higher
`quality work and to provide some level of assurance to end
`users that the individual or organization is qualified to
`perform the job for which they are certified. However, none
`of these certifications actually certifY the end product that
`results from the job.
`Under existing certification programs, an end user may
`have some level of assurance that a particular individual or
`organization is qualified to produce quality software. How- 10
`ever, there is little or no assurance that the resulting software
`is of high quality. Even SEI-CMM level 4 organizations (a
`very mature level on the SEI-CMM scale) can produce
`shoddy software, while same individuals with no explicit
`software engineering process can produce high quality soft- 15
`ware. Certifications of people and processes provide a good
`indicator for the expected quality of software but do not
`speak to the actual quality of the finished product.
`In addition to certification of processes and people, a need
`exists for certification processes that certifY the actual qual- 20
`ity of software. Two major problems face software users and
`consumers alike: (1) a lack of sound metrics for quantifying
`that information systems are trustworthy, and (2) the absence
`of an organization (such as an Underwriter's Laboratory) to
`apply the metrics in order to assess trustworthiness. In fact, 25
`if such problems were solved, software vendors who sought
`to provide reliable products would also benefit due to a
`higher premium or larger customer-based that should result
`from the increased consumer confidence in the vendors'
`wares.
`A number of different efforts have focused on identifying
`vulnerabilities in software or protecting systems from soft(cid:173)
`ware vulnerabilities. For example, as an alternative to source
`code-based analysis, StackGuard, a gee compiler variant for
`Linux developed by the Oregon Graduate Institute, attempts
`to protect buffers from stack smashing attacks by aborting
`the program if the return address pushed on the stack is
`overwritten. StackGuard can prevent stack smashing attacks
`from running arbitrary code embedded in user input, but will
`not protect programs against all buffer overflow attacks. For
`example, buffer overflow attacks that overwrite local vari(cid:173)
`ables that were never intended to be changeable by a user
`can result in security violations not prevented by Stack(cid:173)
`Guard.
`The Fuzz tool is another tool that can be used to identify 45
`and prevent overflow buffers, but it may produce inconclu(cid:173)
`sive results. Because input is randomly generated, the vul(cid:173)
`nerability of the program executing user-defined code can(cid:173)
`not fully be assessed. Similarly, the FIST tool implements
`specific fault injection functions that determine the pro- 50
`gram's vulnerability to specially-crafted buffer overflow
`attacks, but carmot protect against all buffer attacks.
`Various run-time approaches have also been addressed.
`One such approach is dynamic interception of buffer over(cid:173)
`flows by using the libsafe library. While dynamic techniques 55
`can offer some level of run-time protection, they often incur
`a performance penalty. Dynamic approaches are also limited
`to buffer-overflow specific attacks and can make no claims
`about the overall security of the software. While a dynamic
`approach can offer a great safety-net, a static-analysis of the 60
`source code is preferable to assure that code is written in a
`safe and proper manner.
`Another approach that has been examined is the ITS4
`Security Scanner. ITS4 is a simple tool that statically scans
`C and C++ source code for potential security vulnerabilities. 65
`It is a command-line tool that works across Unix environ(cid:173)
`ments. ITS4 scans source code, looking for function calls
`
`The present invention provides a process for certification
`of software applied to essential software systems, such as
`30 those that run e-commerce sites. In particular, the present
`invention provides a process for certifying whether a soft(cid:173)
`ware program is free from a common class of software flaws
`that are often leveraged into security violations. Embodi(cid:173)
`ments of the present invention accommodate many other
`35 classes of security vulnerabilities, as well as other classes of
`software flaws that may have application in other essential
`software systems such as in safety-critical and high-reliabil(cid:173)
`ity applications.
`In an example, a specific embodiment of the present
`40 invention was used to analyze software for vulnerability to
`the most commonly exploited software flaw, the uncon(cid:173)
`strained buffer, which is exploited by the buffer overrun
`attack.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. lA shows a sample program that may be use to
`exploit the well-known buffer overflow vulnerability con(cid:173)
`nected with the strcpy C function.
`FIGS. lB-lD are schematic diagrams showing how the
`program shown in FIG. lA results in a buffer overrun.
`FIG. 2 is a schematic diagram showing the process flow
`for software analysis an certification in an embodiment of
`the present invention.
`FIG. 3 is a chart showing analysis times for stages of a
`pipeline, according to one embodiment of the invention.
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`The present invention provides a certification process for
`application software that enables organizations to deploy
`software in essential applications with greater confidence.
`By implementing a system and method for software certi(cid:173)
`fication according to the present invention a software vendor
`can ensure the software it releases is likely not to fail in a
`
`Blue Coat Systems - Exhibit 1005 Page 7
`
`

`
`US 7,284,274 Bl
`
`7
`way that will compromise system security, safety, reliability,
`and other dependability properties.
`The present invention provides a pipelined approach for
`certifYing software wherein distinct components are
`assembled into a pipeline such that the results of one
`component are used as input for the next component.
`Advantages of such a pipeline are two-fold. First, there is
`the advantage of pipelining the process where multiple
`components can be analyzed simultaneously. H~wever,
`another major benefit is in the ability to use d1fferent
`accuracy levels for each stage of the pipeline. With conven(cid:173)
`tional processes, it is usually the case that, in order to get
`higher degrees of precision in the results, a more computa(cid:173)
`tionally intensive algorithm is needed. Using such algo(cid:173)
`rithms in the first stage would result in extensive computa(cid:173)
`tion times for processing the components. In contrast, a
`pipeline approach according to the present in~ention all_ows
`the use of progressively more complex algonthms chamed
`together so that computationally cheaper algorithms are used
`to progressively filter out false positives in the results, and
`thus the more expensive algorithms can be used on a
`dramatically reduced subset of inputs, reducing the overall
`processing time significantly.
`A pipeline implemented according to the present inve~- 25
`tion is illustrated in FIG. 2. Pipeline 200 has several mam
`modules each of which are supported by the auxiliary
`modules: An Abstract Syntax Tree (AST) of the code being
`examined is generated by preprocessor/parser module 206
`for input into Stages I and II of pipeline 200, as shown in 30
`FIG. 2. Knowledge database 202 stores information regard(cid:173)
`ing the various fault classes to be scanned for. Information
`from knowledge database 202 is fed into Stage I of the
`pipeline: Vulnerability Code Analyzer (VulCAn) 204. Vul(cid:173)
`CAn 204 uses input from knowledge database 202, along 35
`with the AST (obtained from preprocessor/parser module
`206), and nms a context-sensitive algorithm on the input.
`The resulting flagged vulnerabilities are passed on to Stage
`II of the pipeline. In Stage II, static analysis 208 is per(cid:173)
`formed. As shown in FIG. 2, Stage II uses the AST, as well 40
`as the preprocessed code to obtain various graphs that can be
`used as the basis for the analysis.
`In on embodiment of the present invention, pipeline 200
`may be used to analyze several fault classes including buffer
`overruns
`time-of-check-to-time-of-use (TOCTTOU) and 45
`other ty~es of flaws. All the components in the pipeline are
`written so as to allow easy additions of more fault classes to
`scan for. The known fault class definitions are stored in
`vulnerability knowledge database 202, described herein.
`This