Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-02-17
2003-04-15
Metjahic, Safet (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C711S108000
Reexamination Certificate
active
06549903
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to operational methods used by processors and computing devices. More particularly, the invention relates to a method and apparatus for using a data-type tag concatenated to each data word stored in memory to preserve the integrity of a data architecture.
2. Description of the Related Art
The utility of computer processors is primarily evaluated according to three criteria: speed of operation, compatibility with other systems, and reliability. A processor's reliability depends on the data security it provides for programming and system usage. As the size of applications run on such processors has increased over the past years, so has the importance of providing such security. A large program typically consists of a large number of modules or subprograms (hereinafter referred to collectively as “modules”), each of which may have been designed and/or written by a different individual. When such modules interact, security features are necessary to isolate the effects of an error to the module in which it occurred—it should be impossible for an error that originates in a first module to corrupt data used by a second module and thereby interfere with the operation of the second module.
The scope of such security issues is broad, being relevant not only for protecting against innocent errors inadvertently introduced by programmers, but also for safeguarding against deliberately perpetuated malicious actions, such as may be introduced by various computer viruses. Moreover, this concept of providing data security in concert with modularity, while outlined above for an individual program, may readily be extended to encompass preserving safe interaction among multiple programs on a larger scale. A conspicuous example of such a large-scale program interaction is the internet, which can usefully be regarded as a single extended application composed of a large number of interacting programs. With the continued growth of use of the internet, the importance of maintaining data security by isolating the effects of errors to individual modular programs continues to increase.
A useful conceptual framework in which to understand approaches to data security involves “user context.” This refers to all space available to the user, including registers, memory locations, files, etc., which a human user might recognize as variables, arrays, a functions, objects, modules, etc. In a more general sense, user context refers to the space available to any active agent, including a task, program, procedure, etc., in addition to a human user. In this more general sense, the user context for a function would include its local and global variables, functions, and parameters, and as well as those spaces that are pointed to by pointers within those variables and parameters. Within this framework, the requirements for data security discussed above are equivalent to requiring that user context not be expanded.
Methods for limiting user context, i.e. preventing the programs and data of one module from unauthorized access by another module, operate in part by identifying the data type of individual data words. Certain functions (such as moving pointers and descriptors) are prohibited from operating on data words that are not identified with the appropriate data type. Such data-type checking can be performed at different times, depending on the structure of the computer language used. For example, in the case of high-level languages, it is possible to check these data types and grant corresponding data-access rights to the proper modules at the time of compilation. This requires that certain static restrictions be introduced into the language, which make it nonuniversal and adversely affect its efficiency for many applications. In particular, to permit the compiler to check that pointers and descriptors are handled correctly, it is necessary to have statically known variable types that remain constant during the variable's entire life. While this has the modest advantage that data-type checking is completed with compilation of a program, these static variables can only be moved or used for object access, and cannot be used for such operations as arithmetic or logic operations. Despite these deficiencies, several high-level languages, such as Java, adopt this tactic.
A more efficient approach involves checking variable data types dynamically at run time; this can either be done exclusively by software or may be complemented with hardware support to increase the level of efficiency even further. Both of these dynamic approaches are actively used in different languages. A number of languages, such as LISP and Smalltalk, use exclusively software-based run-time checking, which is somewhat simpler to implement but lacks the additional efficiencies possible from including hardware support.
The inclusion of hardware support lends itself to different ways of making use of that support. Common to these different ways is the notion of “capabilities.” A capability is a descriptor that defines the access rights for some operational space. Such a descriptor may, for example, take the form of an array descriptor or a procedure label. With hardware support, user context can be defined by the list of capabilities that the user possesses. In order to limit user context, a capability should be protected from unauthorized modification. To implement data security features, there should therefore be both means for distinguishing capabilities from other data and there should be a mechanism for preventing ordinary data from being used as capabilities.
The most popular approach for implementing data security features with these constraints is use of a “capability list,” which is a tabulation.of data types and corresponding data words stored in separate memory segments. In this approach, all pointers and descriptors are kept in special typed segments and have special operations to work with these segments. Capabilities are kept distinct from other data by imposing requirements on operators that act on data: an operation that acts on a capability (e.g. LOAD or STORE) can only get its operands from the separate memory segments where the capability list is stored; other operations (e.g. ADD or MULTIPLY) can never operate on those separate memory segments. While several processors have been built using this approach, they still suffer from significant inefficiencies, both in speed of operation and in the flexibility afforded to programmers. These inefficiencies are a direct consequence of the restriction inherent in this approach that separate memory segments be used to store the capabilities.
An alternative approach involves the use of data tags, which permit greater flexibility without significant adverse effect on efficiency. In this approach, operational spaces are not separated. Instead, data tags record the data types of data words in extra bits concatenated to each data word. As such, the inefficiency produced from storing capabilities in separate memory segments is avoided. Capabilities are separated from other data by the positioning of the tag with respect to the data words. Also, operations are defined such that only a particular set of data types are permissible for each operand. For example, the LOAD operation could be defined to load both the capability and data in the form of a tagged data word by having two operands, the first restricted to being a capability and the second restricted to being other data. An operation such as ADD would, however, require that both of its operands be numbers.
In modern processors, there is a need to handle both numeric data and non-numeric data, which can be distinguished by using separate tags. However, there has so far been no processor that has used a fully consistent set of capability-based features to provide overall tagged data integrity and protection in an architecture with several non-numeric data formats.
SUMMARY OF THE INVENTION
The present invention is directed to a method and computer
Babaian Boris A.
Gruzdov Feodor A.
Sakhin Yuli K.
Volkonsky Vladimir Y.
Elbrus International Limited
Metjahic Safet
Nguyen Merilyn
Townsend and Townsend / and Crew LLP
LandOfFree
Integrity of tagged data does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Integrity of tagged data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Integrity of tagged data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3052519