`Cline et al.
`
`[54] METHOD FOR ANALYZING CALLS OF
`APPLICATION PROGRAM BY INSERTING
`MONITORING ROUTINES INTO THE
`EXECUTABLE VERSION AND
`REDIRECTING CALLS TO THE
`MONITORING ROUTINES
`[75] Inventors: David C. Cline, San Jose; Andrew P.
`Silverman, Los Gatos; Farrell W,
`Wymore, Mountain View, all of
`cam
`[73] Asslgnee: 28(1),?“ Consortium’ Ltd" Sunnyvale’
`a 1 ‘
`[21] Appl. No.: 584,189
`[22] Filed:
`sep. 18, 1990
`
`[51] Int. Cl.5 ....................... .. G06F 11/30; G061= 9/45
`U.S. Cl. .................................. ..
`395/700; 371/19; 364/2745; 364/2804;
`364/2805; 364/2641; 364/DIG- 1
`_
`[58] Field Of Search ............. .. 395/500, 575, 600, 700,
`395/800; 371/19
`
`[56]
`
`,
`
`,
`
`lll'gCI'SO?
`
`References Cited
`Us PATENT DOCUMENTS
`5
`gambach ----------------------------
`4,642.765 2/1987 Cooke et all
`4,692,897 9/1987 Crabbe, Jr. .... ..
`4,951,195 8/1990 Fogg’ Jr’ at a].
`5,047,919 9/1991 Sterling et al.
`5,204,956 4/1993 Danuser et al. . . l .
`
`;
`395/700
`371/251
`395/500
`395/575
`. . . .. 395/575
`
`US005313616A
`5,313,616
`[11] Patent Number:
`[45] Date of Patent: May 17, 1994
`
`5,210,862 5/1993 De Angelis et al. .............. .. 395/575
`5,212,794 5/1993 Pettis et al. ........ ..
`395/700
`
`OTHER PUBLICATIONS
`Joseph et al, “A Fault Tolerance Approach To Com
`puter Viruses”, IEEE, Apr. 1988, pp. 52-58.
`Primary Examiner-Thomas C- Lee
`Assistant Examiner-Paul Harrity
`Attorney, Agent, or Firm-Fish & Richardson
`[57]
`ABSTRACT -
`A method for verifying the conformance of an applica
`tion program to a set of system rules characterized by
`the development of a conformance database, the perfor
`mance of a static analysis of .theapplicatlon program to
`determine whether the application program 15 in static
`conformance with the conformance database and the
`performance of a
`analysis of the application
`program to determine whether the application program
`is in dynamic conformance with the conformance data
`base_ The Static analysis produces a graph of the basic
`blocks of the application program and analyzes the
`graph for conformance to system rules, dead code and
`coverage metrics. ‘The dynamic analysis adds a small
`amount of monitoring code into an executable applica
`tion program which monitors the application program
`as ltd“ i’s‘egcllfd 1; i’ Lest In??? The g‘°mt°{mg:"fde
`pm 9°
`g a a _a§e W ‘C can, 8,3“ We °r
`run-time non-conformities of the application program.
`
`‘
`
`'
`
`‘
`
`'
`
`‘
`
`‘
`
`11 Claims, 15 Drawing Sheets
`
`insert Monitoring Code into
`Application Executable Code
`
`60
`_/
`
`'
`r'ioni tor and Record System
`and Procedure Calls
`
`7
`Process the System and
`Procedure Call Data Externally
`to the Application Program
`
`62
`
`64
`
`Blue Coat Systems - Exhibit 1003
`
`
`
`US. Patent
`
`May 17, 1994
`
`Sheet 1 of 15
`
`5,313,616
`
`/=
`
`1a
`
`to 55 @996 5:328
`
`
`
`
`at E @3828 12:3
`
`
`muO wIP O._. o2< mum
`
`w .wi
`
`
`
`U.S. Patent
`
`May 17, 1994
`
`Sheet 2 of 15
`
`5,313,616
`
`[N
`
`N .wE
`
`@
`
`
`
`muO wIP Qz< mum
`
`D /a
`
`
`
`US. Patent
`
`May 17,1994
`
`Sheet 3 of 15 '
`
`5,313,616
`
`PRODUCE A HIGH LEVEL
`DESCRIPTION OF
`SYSTEM CALLS AND
`PROCEDURE CALLS
`(BCS AND OCS)
`
`COMPILE TO PRODUCE
`OBJECT LEVEL FILES
`
`LINK FILES TO PRODUCE
`MACHINE LEVEL
`DATABASE FILE
`
`CLEAN UP MACHINE LEVEL
`DATABASE FILES TO PRODUCE
`CONFORI'IANCE DATABASE
`
`Fig. 3
`
`
`
`US. Patent
`
`May 17, 1994
`
`Sheet 4 of 15
`
`5,313,616
`
`OEuN
`
`x2:
`
`352.6% mm $22,522
`
`HEE // 2.;
`
`mm :5 mm j<u lllllll
`
`
`55% $5510 55% E55
`
`8 NEE : ma>t mm .- :5
`
`on
`
`
`
`in 239m 2396
`
`RV
`
`2%
`
`vi:
`
`ow .. :5
`
`amm
`
`
`
`US. Patent
`
`May 17, 1994
`
`Sheet 5 of 15
`
`5,313,616
`
`Cam-N
`
`vi:
`
`m .5
`
`OKmN
`
`v2..
`
`MEDQMUOQQ
`mm
`
`
`
`US. Patent
`
`May 17, 1994
`
`Sheet 6 of 15
`
`5,313,616
`
`SOURCE 1
`
`SOURCE 2
`
`comma: 1
`
`COMPILER 2
`
`OBJECT 1
`
`'
`
`OBJECT 2
`
`36
`SYSTEM /
`LIBRARY
`
`EXECUTABLE BINARY
`APPLICATION PROGRAMS
`
`Fig. 6
`
`
`
`US. Patent
`
`May 17, 1994
`
`Sheet 7 of 15
`
`5,313,616
`
`ANALYZE OBJECT CODE
`OF APPLICATION PROGRAM
`TO DETERMINE BASIc BLOCKS
`
`38
`/
`
`40
`'OEFINE THE REGISTER
`SETS FOR EACH BASIC BLOCK -/
`
`BUILD A GRAPH FROM THE
`BASIC BLOCKS
`
`42
`_/
`
`PERFORM FRAME ANALYSIS /
`
`I
`
`INVERT THE GRAPH
`
`PERFORM OEAO CODE “~48
`ANALYslswpTloNAL)
`
`PERFORM cALL ANALYSIS‘ /
`
`
`
`US. Patent
`
`May 17, 1994
`
`Sheet 8 of 15
`
`5,313,616
`
`OneEntrance
`
`39
`
`Basic Block
`(Executes all
`Instructions)
`
`One or Two Ex its
`
`Fig. 8
`
`
`
`US. Patent
`
`May 17, 1994
`
`Sheet 9 of 15-
`
`5,313,616
`
`ROOT
`
`ROUTINE
`
`54
`
`LEAF NODES
`
`Fig. 9
`
`
`
`US. Patent
`
`May 17, 1994
`
`Sheet 10 of 15
`
`5,313,616
`
`O
`
`F4
`‘II-1
`
`bb
`[L
`
`‘II-l
`
`2 ‘.5
`
`
`
`U.S. Patent
`
`May 17, 1994
`
`Sheet 11 of 15
`
`5,313,616
`
`50
`Insert Monitoring Code into
`Application Executable Code J
`
`Monitor and Record System
`and Procedure Calls ' J
`
`62
`
`Process the System and
`Procedure Call Data Externally
`to the Application Program
`
`64
`
`Fig. 12
`
`
`
`US. Patent
`
`May 17,1994
`
`Sheet 12 of 15
`
`5,313,616
`
`BUILD HASH TABLE FROM
`CONFORHANCE DATABASE
`
`66
`
`Y
`PROCESS APPLICATION PROGRAM
`
`68
`
`,
`ASSEMBLE AND OUTPUT
`INSTRUMENTED APPLICATION
`PROGRAM _
`
`70
`
`Fig. 13
`
`
`
`US. Patent
`
`May 17, 1994
`
`Sheet 13 of 15
`
`5,313,616
`
`PROCESS APPLICATION PROGRAM AND
`DETERMINE ITS SIZE
`
`I
`
`RELOCATE SPY.O OBJECT MODULE TO THE
`END OF THE APPLICATION PROGRAM
`
`I
`
`DETERMINE THE SIZE OF THE RELOCATED
`OBJECT ‘ MODULE
`
`BUILD THE PROGRAM SYMBOL TABLE
`
`I
`
`CATEGORIZE PROCEDURE NAMES INTO
`SYSTEM SYMBOLS AND USER SYMBOLS
`
`I
`
`SCAN APPLICATION PROGRAM FOR
`PROCEDURE cALLs, MAKE A LIST
`BY LOCATION AND TARGET AND
`PRODUCE A STUB FOR EACH PROCEDURE
`
`I
`
`SCAN APPLICATION PROGRAM FOR
`SYSTEM CALLS AND SYSLOCAL CALLS
`AND GENERATE STUB FOR EACH TRAP
`INSTRUCTION
`
`86
`
`I
`
`' DETERMINE THE TOTAL STUB SIZE
`
`Fig. 14
`
`
`
`US. Patent
`
`May 17, 1994
`
`Sheet 14 of 15
`
`5,313,616
`
`88
`\- ADD SPY.O OBJECT T0 TEXT
`
`1
`l
`l
`$
`
`90
`\. MOVE DATA SECTION TO
`64K BOUNDARY
`
`ADD SPY.O DATA To
`92
`\ DATA SECTION
`
`94
`\. MODIFY HEADER
`
`96
`\ MODIFY TExT TO
`- CALL STUBS
`
`MODIFY 5910 WITH
`98
`\ LOCATIONS 0F SELECTED
`STRUCTURES
`
`l
`
`100
`
`DEVELOP A BIT VECTOR
`OF USER PROCEDURES
`
`1
`
`FILL OUT THE DATA
`102
`\‘ SECTIONS WITH NULLS
`
`C
`
`Flg. 15
`
`
`
`US. Patent
`
`May 17, 1994
`
`Sheet 15 of 1s -
`
`5,313,616
`
`TEXT
`
`DATA
`
`BSS
`
`STACK
`
`TEXT
`
`SPY.O
`
`STUBS
`
`SPY.O DATA
`
`NODULO
`
`64K
`
`DATA
`
`B55
`
`STACK
`
`Fig. 16b
`
`
`
`1
`
`METHOD FOR ANALYZING CALLS OF
`APPLICATION PROGRAM BY INSERTING
`MONITORING ROUTINES INTO THE
`EXECUTABLE VERSION AND REDIRECTING
`CALLS TO THE MONITORING ROUTINES
`
`5
`
`25
`
`5,313,616
`2
`ing the structure and operation of the computer system
`are published and are typically made available free of
`charge or for a modest licensing fee. Examples of open
`standard systems include systems which use the MS
`DOS operating system of Microsoft, Inc. or certain
`versions of the UNIX system from AT&T. In theory,
`application developers would rather produce applica
`tion software for open standard systems than propri
`etary standard systems due to a potentially larger num
`ber of systems which could run their software. The
`advantage for hardware and operating system vendors
`in conforming their systems to open standards is that
`they will probably have a larger base of application
`software available to their customers and may therefore
`sell more of their hardware platforms and operating
`systems.
`When a new computer architecture is developed it
`can be decided whether it should adhere to proprietary
`or open standards. For example, the relatively new
`reduced instruction set computer (RISC) processors
`available from such companies as Sun Microsystems,
`MIPS, AMD and Motorola can be designed into sys
`tems which operate under proprietary standards or can
`be designed into systems which operate under more
`open standards. The trend with RISC processors is to
`design them into systems which utilize some form of
`UNIX, making them compatible with other such sys
`tems at least at the UNIX source code level which is
`typically written in the language C. However, even
`computer systems having the same RISC processor and
`running under a version of UNIX are probably not
`compatible at the object module or binary code level
`due to incompatible uses of the processors registers,
`ports and memory interfaces. If a number of vendors
`wish to produce a truly open standard system, it is
`therefore necessary that they agree upon certain design
`and operating rules so that an application program
`which conforms to the same design and operating rules
`will run on all conforming systems.
`A problem encountered with such an approach is
`how to ensure that an application program which is
`supposedly designed according to the standard rules
`will actually operate on systems provided by a number
`of manufacturers. For example, certain application pro
`grams written for the MS-DOS operating system will
`not work on some PC-clones because the hardware is
`not 100% compatible. As another example, some UNIX
`applications will work only with certain versions of the
`UNIX operating system. There is therefore a need in
`the software industry for procedures which can verify
`that application software developed in conformance
`with a set of accepted design rules will operate with
`computers and operating systems from any vendor
`which also adopts those design rules.
`
`BACKGROUND OF THE INVENTION
`This invention relates generally to computer software
`and more particularly to software designed to test appli
`cation programs.
`A digital computer system includes both hardware
`and software. The hardware includes the physical por
`tions of the computer system such as the central pro
`cessing unit (CPU), memory, input/output (I/O) ports
`and peripherals. The software portion of the system
`comprises a sequence of instructions stored in memory
`which direct and control the operation of the hardware.
`The computer system’s software includes both sys
`tem and application software. The system software,
`often referred to as the “operating system”, interacts
`directly with the hardware of the computer system to
`perform such functions as storing data to memory, in
`putting and outputting data and manipulating the regis
`ters of the CPU. Application software interfaces with
`system software and typically performs user-speci?c
`applications such as spreadsheet analysis, word process
`ing and computer aided design (CAD).
`A problem encountered by application software de
`velopers is that application software developed to work
`with a particular operating system will almost certainly
`not work with other operating systems, even if these
`alternative operating systems are closely related an
`operate on similar hardware platforms. Application
`software developers therefore tend to write application
`programs for the most common operating systems to
`maximize the potential size of their market. After appli
`cation software has been developed for a particular
`operating system it may, with varying degrees of effort,
`be modified or “ported" to run on other operating sys~
`terns.
`Another problem encountered by software develop
`ers is that hardware from different vendors tends to be
`different in architecture even if they are using the same
`operating system. Since many application software de
`.45
`velopers bypass the operating system to increase system
`performance, their application software may not run on
`all hardware platforms which support the operating
`system. In these circumstances software developers
`have several choices: 1) they can choose not to bypass
`the operating system and accept lower performance of
`their application program; 2) bypass the operating sys
`tem but only support the most common hardware plat
`form; or 3) bypass the operating system and port the
`‘application program to support multiple hardware plat
`forms.
`There is a trend in the industry towards computer
`systems designed around open standards rather than
`proprietary standards. In proprietary standard systems
`the structure and operation of the computer system is
`owned and protected by a particular vendor with a
`combination of patents, trade secrets and copyrights.
`Proprietary system manufacturers tend not to license
`others to make systems which would compete with
`their own. Examples of proprietary systems include
`computer systems manufactured by Digital Equipment
`Corporation, Apple Computers, Inc. and Wang Labora
`tories. In open standard systems certain details concern
`
`35
`
`SUMMARY OF THE INVENTION
`The present invention certifies that tested and veri
`fled application programs will run on any hardware and
`operating systems which were designed in conformance
`with a set of system rules. This invention therefore
`allows application program developers to produce soft
`ware which conforms to open standards, thereby
`greatly increasing the potential market for their applica
`tion programs.
`A method for certifying the portability of software
`between computer systems begins with the develop
`ment of a set of system rules. Hardware manufacturers,
`
`60
`
`65
`
`
`
`20
`
`25
`
`5,313,616
`4
`3
`operating system developers and application program
`FIG. 3 is a flow diagram of a method for producing
`developers all produce products which comply with
`a conformance database;
`FIG. 4 is a diagram of a system call structure of the
`these system rules. Certi?cation tests are then run to
`conformance database;
`ensure that the application programs will run on any
`conforming computer system regardless of the vendor.
`FIG. 5 is a diagram of a procedure call structure of
`the conformance database;
`The certi?cation tests include a static analysis and a
`dynamic analysis of the application program. First, a
`FIG. 6 is a diagram used to illustrate the various
`conformance database is developed which includes
`levels at which static analysis can be performed on an
`application program;
`allowable external calls, such as system calls and proce
`FIG. 7 is a flow diagram of a method for static analy
`dure calls. Then a static analysis is performed which
`analyzes the object code of an application program to
`sis of an application program;
`FIG. 8 illustrates a basic block of an application pro
`determine whether any illegal or erroneous external
`calls are being made. Finally, a dynamic analysis of the
`gram;
`program is performed which analyzes the application
`FIG. 9 is a graph of a forest of basic blocks;
`FIG. 10 is a graph of a tree which results from the
`program as it is being run to determine any runtime
`removal of dead code from the forest of FIG. 9;
`errors in the calls made by the application program. If
`FIG. 11 is a graph after the tree of FIG. 10 has been
`no errors are detected in either the static analysis or the
`pruned;
`dynamic analysis then the application program is certi
`FIG. 12 is a ?ow diagram a method for dynamically
`?ed to be compatible with the set of system rules and is
`analyzing an application program;
`transportable without change between all certi?ed com
`patible computer systems.
`FIG. 13 is a flow diagram detailing the insert moni
`toring code step of FIG. 12;
`A preferred method for static analysis converts an
`FIG. 14 is a flow diagram detailing the process appli
`object code version of the application program into a
`graph of basic blocks, inverts the graph and analyzes
`cation program step of FIG. 13;
`FIG. 15 is a ?ow diagram detailing the assemble and
`the inverted graph for errors and external calls which
`output step of FIG. 13;
`do not conform to the system rules. As an option, dead
`FIG. 16a illustrates the application program structure
`code analysis and basic block coverage can also be
`prior to dynamic instrumentation; and
`performed on the graph.
`The dynamic analysis is accomplished by adding a
`FIG. 16b illustrates the application program structure
`after instrumentation.
`small amount of monitoring code to the application
`program and verifying system and procedure calls and
`determining program coverage as the application pro
`gram executes a test program. The monitoring code
`creates a log database which is used by a separate
`"post” program to print a report of call usage and pro
`gram coverage after the completion of the application
`program run.
`After the static analysis and the dynamic analysis
`indicates conformance to the predetermined set of sys
`tem rules the application program can be certi?ed to be
`statically and dynamically compatible with all certi?ed
`computer systems. Furthermore, the application will be
`compatible with future hardware platforms and operat
`ing systems which are also designed in conformance
`with the set of system rules thereby achieving genera
`tional portability. The application program needs to be
`tested on only one certi?ed computer system to attain
`compatibility certi?cation for all current and future
`generations of certi?ed computer systems.
`An advantage of de?ning the portability standards in
`advance of hardware and software design is that hard
`ware/software development work can progress concur
`rently. For example, a software application for a partic
`ular vendor’s hardware system can be written and veri
`?ed on other conforming systems before that vendor’s
`hardware system is available.
`These and other advantages of the present invention
`will become clear to those skilled in the art upon a study
`of the detailed description of the invention and of the
`several ?gures of the drawings.
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS
`In FIG. 1 a flow diagram illustrates a basic process
`for certifying the portability of software between com
`puter systems. In a ?rst step 10, as set of system compat
`ibility rules including a binary compatibility standard
`(BCS) and an object compatibility standard (OCS) are
`developed. By “binary", "binary code”, “binary level"
`or the like it is meant that the program is in the execut
`able machine code language of a computer system’s
`CPU. By “object", “object code”, “object level”, “ob
`ject module” or the like it is meant the program has
`been assembled into machine code but has not been
`linked and otherwise processed to the stage where it is
`directly executable by the computer system’s CPU.
`In a step 12 of FIG. 1, a number of computer system
`vendors produce computer systems which conform to
`both the BCS and the OCS. In a step 14, software devel
`opers write application programs which conform to the
`BCS and the OCS to ensure that their application pro
`gram will run on any vendor’s certi?ed compatible
`computer system.
`It should be noted that the steps 12 and 14 of FIG. 1
`can occur concurrently or sequentially. Since the BCS
`and the OCS specify a de?ned interface in as predeter
`mined set of system rules, system compatibility is en
`sured as long as the hardware system, operating system
`and application programs follow the de?ned interface.
`In many cases, hardware, operating system and applica
`tion program development occur in parallel to minimize
`the time to market for a complete system.
`The present invention has been reduced to practice
`on computer systems based upon the Motorola 88000
`series of RISC microprocessors and more particularly
`upon the Motorola MC88l0O microprocessor. A man
`ual describing the MC88100 microprocessor is available
`from Motorola, Inc. as “MC8810O RISC MICRO
`
`30
`
`35
`
`45
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 is a flow diagram of a method for producing
`portable application programs which conform to a set
`of system rules;
`FIG. 2 is a flow diagram ofa method for verifying the
`conformance of an application program to a set of sys
`tem rules;
`
`65
`
`
`
`6
`TABLE 2-continued
`An OCS Procedure Call Speci?cation
`SYNOPSIS
`int readlink (path, buf, bufsize)
`char ‘path;
`char 'buf;
`int bufsize;
`REFERENCE
`For description, see BCS RLI. 9.73
`
`5,313,616
`5
`PROCESSOR USER’S MANUAL, Second Edition,
`MC88l00UM/AD, Rev. 1.
`A BCS in accordance with the present invention has
`been developed for the MC88100 microprocessor
`which de?nes the minimum interface which must be
`supported in the hardware and operating system to
`maintain conformance with a set of system compatibil
`ity rules. An OCS has also been developed for the same
`microprocessor which de?nes the minimum interface
`for system libraries and procedures. It should be noted
`that the BCS and the OCS are not an exclusive list for
`hardware and operating system vendors: they can de
`sign their systems to include features which are not
`included in the BCS and OCS as long as their systems,
`at a minimum, support all of the features of the BCS and
`the OCS.
`A manual describing the BCS is available from the
`88open Consortium Ltd., 2099 Gateway Place, Suite
`300, San Jose, Calif. 95110 as Binary Compatibility Stan
`dard (BCS), release 1.1, April 1990. The BCS manual
`speci?es the BCS for systems based upon the Motorola
`MC8810O and future related microprocessors. It pro
`vides for the portability of application software at the
`binary level by specifying interfaces between the binary
`?le and the operating system and by providing data
`interchange standards for installing software from re
`movable media. The BCS manual de?nes ?le formats
`and the data structures, system call numbers and return
`registers for the allowable system commands. An exam
`ple of a BCS system call speci?cation taken from page
`60 of Binary Compatibility Standard (BCS) is shown
`below in Table 1:
`
`In FIG. 2 a ?ow diagram illustrates a process for
`verifying the conformance of application programs to
`the set of system compatibility rules. In a ?rst step 16, a
`conformance database is developed from the BCS and
`the OCS. A static analysis is made of the executable
`binary code or an object module of the application
`program in a step 18 to determine whether there are any
`static violations of the system compatibility rules. Also,
`a dynamic analysis is made in a step 20 to determine
`whether there are any run-time violations of the system
`compatibility rules. If neither the static analysis nor the
`dynamic analysis detect incompatibilities the applica
`tion can certi?ed as statically and dynamically compati
`ble with any certi?ed compatible computer system.
`Additional tests may also be run to detect other forms of
`system compatibility such as magnetic tape format com
`patibility, network compatibility, etc.
`When presented with an object module, SBV utilizes
`the OCS rules and when presented with an executable
`SBV utilizes the BCS rules. DBV, as a default, always
`uses the BCS rules since it deals with executables. As a
`debugging option, both SBV and DEV can be made to
`apply OCS rules to executables.
`FIG. 3 is a ?ow diagram of the develop conformance
`database step of FIG. 2. In a ?rst step 22, the BCS and
`the OCS rules are input into a computer system in a
`high-level database description language. The database
`description language is compiled to produce object
`level ?les in a step 24 and the ?les are linked in a step 26
`to produce a raw conformance database ?le at the bi
`nary level. Finally, the raw conformance database ?le is
`cleaned in a step 28 to produce the conformance data
`base ?le used in the statici'and dynamic analysis steps.
`This cleaning step recognizes the fact that whenever
`you describe a large, complex database in a high-level
`language that errors will be present in the compiled
`code. System test are run which exercise every portion
`of the database to identify these errors for correction or
`removal from the database.
`The conformance database ?le of the present inven
`tion which includes BCS and OCS rules includes more
`than 9000 lines of code. A small subset of the source
`code of the conformance database ?le as developed in
`step 22 is shown below in Table 3.
`TABLE 3
`Portion of Source Code for Conformance Database File
`LEVELS BCS, STREAMS, TAPE, BCSNA, BCSLK,
`BCSJCTL, OCS, OCSNA, OCSXA,
`OCSLK, OCSJCTL
`MAX_PID = 32000
`FD_MAX = 25
`
`O_NDELAY. O_NONBLOCK. O_APPEND,
`O_TRUNC, O_EXCL, O_NOCTTY,
`O__SYNC }
`- note openset 2 is same as opensetl with addition of O_.CREAT
`openset2 = { O_RDONLY. O_WRONLY, 0_RDWR.
`
`TABLE 1
`A BCS System Call Speci?cation
`9.3 chdir - Change Current Working Directory
`9.3.1 Synopis
`int chdir(path)
`char ‘path;
`9.3.2 Description
`The chdir ( ) system call causes the named directory to become
`the current working directory, that is. the starting point for path
`searches of pathnames not beginning with slash.
`9.3.3 Data Structures
`None.
`9.3.4 Data De?nitions
`None.
`9.3.5 System Call Number
`3
`9.3.6 Return Register
`
`9.3.7 References
`See the POSIX section 5.2.] description of the chdir ( ) function.
`
`35
`
`45
`
`A manual describing the OCS is available from the
`88open Consortium Ltd. as Object Compatibility Stan
`dard (OCS), release 1.1, April 1990. The OCS manual
`55
`speci?es the object compatibility requirements for con
`forming systems based upon the Motorola MC88100
`microprocessor and future related microprocessors.
`Among the standards speci?ed are the assembly lan
`guage syntax, low level interfaces, object ?le formats
`and the various library calls. An example of an OCS
`procedure call taken from page 201 of Object Compati
`bility Standard (BCS) is shown below in Table 2:
`TABLE 2
`An OCS Procedure Call Speci?cation
`
`65
`
`8.1.5.317 readlink
`NAME
`readlink - read value of a symbolic link
`
`
`
`mode_t = {
`
`7
`TABLE 3-continued
`Portion of Source Code for Conformance Database File
`O_NDELAY, O__.NONBLOCK, O_.APPEND,
`O_TRUNC, O_EXCL, O_NOC'ITY,
`0_SYNC, 0_CREAT }
`S_IRUSR, S._IWUSR, S_IXUSR, S_IRGRP,
`S_.IWGRP, S_lXGRP, S_IROTH, S._IWOTH.
`S_IXOTH, S_ISUID, S_ISGID, S_ISVTX ]
`SYSCALI. getpid 20 BCS
`ARG path PATH
`SRG oflag opensetZ
`ARG mode mode_t
`RETURNS fd_ret_t
`ENDCALL
`SYSCALL open 32 BCS
`ARG path PATH
`SRG on?ag opensetl
`RETURNS fd_ret_t
`ENDCALL
`PROC open OCS
`ARG path PATH
`
`RETURNS int
`ENDPROC
`PROC open OCS
`ARG path PATH
`SRG ollag openset2
`ARG mode mode_t
`RETURNS int
`ENDPROC
`
`10
`
`15
`
`25
`
`The partial conformance database source code listing of
`Table 3 uses the following formats:
`
`De?nitions are given by
`Ranges are given by
`v
`Lists are given by
`Bit sets are de?ned by
`
`NAME=value
`NAME=[rnin. . . max]
`NAME=vall, val2, .
`. ., valn
`
`NAME={bitmaskl, bitrnask2. .
`
`bitmaskn}
`
`. .,
`
`35
`
`and are terminated by
`
`5,313,616
`.
`8
`unique system call number in the BCS rules which is
`passed in register 9 of the MC88100. Each system call
`includes a pointer which points to a data object, such as
`a data object 32, which describes that call type. If a
`system call has several “?avors” or types, the system
`call pointer table will point to the ?rst type data object
`for that system call, the ?rst type data object with point
`to the second type data object for that system call, etc.
`The ?nal type data object for the system call will termi
`nate in a zero link or null to indicate that there are no
`further types of that system call.
`For example, in FIG. 4 the call number 32 corre
`sponds to the system call open( ). This system call has
`two ?avors or types, namely, a two argument type and
`a three argument type. A ?ag bit “O_CREAT” differ
`entiates between the two. The system call pointer table
`will point to a ?rst data object which describes the ?rst
`type of open( ) call and the ?rst data object will point to
`a second data object which describes the second type of
`open( ) call. The second data object terminates in a zero
`link to indicate that no further types of open( ) are speci
`?ed within the system call data structure. As another
`example, the call number 40 corresponds to the system
`call read( ). This system call has only a single type, so
`there is only one data object pointed to by the system
`call pointer table.
`The data objects within the database include a list of
`acceptable arguments, their ranges and which subsets of
`the standards are required to use it. For example, if an
`application program utilizes networking or X-windows
`the conformance database can be used to ensure the
`conforming use of those features. This list of required
`- options is used to ensure that the target system will
`execute the application program, i.e. the “required op
`tion list” is part of the application’s certi?cation. For
`example, an application might be certi?ed to run on
`systems which support the symbolic link feature. If the
`target system does not support symbolic links, the appli
`cation will not run.
`As another example, some system calls include op
`tions which are supported by the standard if they are set
`up properly. The open( ) system call is an example of
`this. The system rules specify that a conforming operat
`ing system must support a minimum of twenty-?ve open
`?les. A conforming application program must not use
`more than twenty-?ve open ?les to ensure portability
`unless the application program ?rst checks with the
`operating system to see if more open ?les are allowable.
`In other words, an open( ) command for a twenty-sixth
`?le is invalid if the operating system is not checked, but
`may be valid if the operating system is checked and
`supports more than twenty-?le open ?les. The confor
`mance database keeps track of such options.
`It should be noted that some of the option checking is
`test speci?c, i.e. it may not be implemented in both SBV
`and DBV. For example, the option checking for the
`open( ) command described above is DBV speci?c,
`although conformance levels are common to both SBV
`and DBV. The important point is that the application
`program must adhere to the list of required options to
`ensure that the target system will properly execute the
`program.
`In FIG. 5, the data structure for the procedure calls is
`different from the data structure for the system calls.
`Unlike system calls, procedure calls are called by name
`rather than by call number. It should be noted that
`application programs typically always make procedure
`calls rather than system calls. For example, an applica
`
`Comments are prefaced by
`the end of the line.
`In Table 3, both system calls and procedure de?ni
`tions are shown. SYSLOCAL de?nitions are not shown
`in Table 3, but are similar to system calls with the addi
`tion of a vendor ID parameter. PATH is a built-in type,
`i.e. one which is known to the database compiler.
`Each of the system calls is given a system call num
`ber. For example, getpid( ) is assigned system call #20
`and open( ) is given system call #32. The fact that there
`are two SYSCALL and two PROC entries for open( )
`indicates that open( ) is a variable argument system call
`where the number or types of its arguments is depen
`dent upon the value of another argument. The argument
`which determines the call form is identi?ed by the SRG
`(Special aRGument) instead of the ARG (ARGument)
`preceding the argument description in the database
`entry.
`FIGS. 4 and 5 illustrate the a preferred data structure
`for the conformance database ?les. More speci?cally,
`FIG. 4 shows the data structure for system calls while
`FIG. 5 shows the data structure for procedure or li
`brary calls. These data structures are produced from the
`high level database language of step 22 by a database
`compiler. The compilation in the present embodiment is
`accomplished in several steps: the high level database
`language is ?rst compiled into assembly language and
`then it is assembled into object modules which can be
`ultimately linked to form the database.
`I
`In FIG. 4, the ?rst portion of the system call data
`structure is a pointer table 30 of system call numbers. As
`mentioned previously, each system call is assigned a
`
`45
`
`55
`
`65
`
`
`
`9
`tion developer will make the command “open( )" which
`will call a library routine which ultimately resolves
`down to the system call #32.
`The set of rules used to analyze the call is dependent
`upon the format of the application program being ana-
`lyzed. If the application is provided as object code, then
`the OCS rules apply. If the application is provided in
`binary form, then the OCS rules don’t apply and the
`BCS rules are used for certification. It is therefore nec-
`essary to analyze the manner in which OCS libraries
`make system calls and the manner in which binary pro-
`grams make system calls.
`As mentioned previously, procedure calls are called
`by name. Since there are potentially thousands of differ-
`ent procedure calls it is desirable to have a process for
`quickly identifying the data objects corresponding to a
`particular procedure call. In the present embodiment,
`an “open addressing” form of hashing is used to quickly
`identify the desired procedure call. The hash table is
`formed by mathematicall