Code verification by tree reconstruction

Details Code verification by tree reconstruction Code verification by tree reconstruction

1999-08-27

2003-07-15

Iqbal, Nadeem (Department: 2184)

Error detection/correction and fault detection/recovery

Data processing system error or fault handling

Reliability and availability

C717S152000

Reexamination Certificate

active

06594783

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates generally to the verification of computer code and, more particularly, to the verification of a code sequence.
2. Related Art
Verification allows computer code from an unknown and potentially untrusted source to be executed on a trusted computer platform avoiding certain classes of potentially serious execution errors. Verification is typically not required for commercially distributed software that is certified by the manufacturer or distributor for “safe” execution on a particular computer platform. Similarly, computer code distributed in source form and compiled locally (i.e., on the machine on which it is to be executed), typically does not require verification as error detection can be performed as part of the compilation process.
However, the increased availability of portable compiled code brought about by the increasing popularity of the Internet and the World Wide Web has made code verification an important concern for on-line users. The JAVA programming language, for example, is intended to provide single source computer code executable on a variety of hardware platforms, provided that a JAVA Virtual Machine (JVM) is present on the platform to interpret JAVA bytecodes into the instruction set of the specific hardware platform. While such characteristics make JAVA an ideal platform for code distributed over the Internet, they also render verification of code downloaded over the Internet a primary concern to ensure users' security on individual platforms.
While verification can be performed at run time, the resulting performance penalty is undesirable for most purposes. Sun's solution to JAVA bytecode verification relies on a technique known as symbolic execution. Symbolic execution, however, presents a number of limitations. First, all possible execution paths in the code must be verified, just in case that portion of the code is exercised at run time. Second, symbolic execution maintains little or no state information about the structure of the code being verified. As a result, when multiple execution paths split and rejoin all possible states of each of the paths must be accounted for. Similarly, loops need to be symbolically executed multiple times if invoked in different code sequences. As a result, symbolic execution is hard to implement and is inherently dependent on a specific bytecode instruction set.
In addition, the only information derived from the symbolic execution process is whether a specific bytecode sequence is accepted or rejected.
SUMMARY OF THE INVENTION
The system and method of the present invention allow for improved code sequence verification through the use of an abstract syntax tree. This is accomplished by first constructing an abstract syntax tree from the code sequence and then determining whether the abstract syntax tree satisfies a predefined set of conditions indicative of the code sequence being executable on the computer without generating a predefined class of execution errors.
The abstract syntax tree is constructed by reassembling the code sequence into a plurality of instructions, combining the instructions into a plurality of blocks, examining the blocks to determine entry points of a plurality of loops, and tagging locations in the series of instructions where control is transferred at the end of each loop. The instructions, blocks, loops and tagged locations are then examined to generate a plurality of control structures (the coarse structure). Finally, the instructions, blocks, loops, tagged locations and control structures are examined to generate a plurality of form expressions (the fine structures).
Since the abstract syntax tree closely approximates the structure of the source code from which the code sequence was generated, the system and method of the present invention overcome the limitations of the prior art. Once the abstract syntax tree has been constructed, verification can be conducted in a more straightforward manner. Since the abstract syntax tree provides more extensive state information, only the tree and not every single path through the code need to be verified. Furthermore, verification on the abstract syntax tree is largely independent from the specific bytecode instruction set.
In addition, since the abstract syntax tree provides the structure of the code sequence, code segments can be inserted into the code sequence to perform additional functions at run time without requiring access to the source code or recompilation.


REFERENCES:
patent: 5317509 (1994-05-01), Caldwell
patent: 5546522 (1996-08-01), Nishida et al.
patent: 5668999 (1997-09-01), Gosling
patent: 5740441 (1998-04-01), Yellin et al.
patent: 5748964 (1998-05-01), Gosling
patent: 5812851 (1998-09-01), Levy et al.
patent: 5963739 (1999-10-01), Homeier
patent: 6061513 (2000-05-01), Scandura
patent: 6110226 (2000-08-01), Bothner
patent: 6314562 (2001-11-01), Biggerstaff
Timobe et al., Device and method for aiding development of application generator, Jan. 12, 2001, NEC Corp., Pub. No. JP02001005655A, pp. 1-1.*
Lim et al., Compiler with generic front end and dynamically loadable back ends, Oct. 2, 1996, Pub. No. EP 000735467A2, Sun Microsystems, pp. 1-1.*
Nakadokoro et al., Program development supporting system, Oct. 18, 1986, Hitachi Ltd, Pub. No. JP361234435A, pp. 1-1.*
Bokowski B et al.: A Front-End for Jave Technical Report B-987-09, XX, XX, Dec. 1998 (Dec. 1998), page complete XP002153552.
Kistler t et al.: “a Tree-Based Alternative to Jave Byte-Codes International Journal of Parallel Programming, Feb. 1999, Plenum, USA”vol. 27, No. 1, pp. 21-33, Xp022009125 ISSN: 0855-7458.

Affiliated with

Also associated with

Rating

Code verification by tree reconstruction does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Code verification by tree reconstruction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Code verification by tree reconstruction will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3092625