waashk/acm huggingface dataset:
addressing security for object-oriented design and ada 95 development during the 1990s, we have seen an explosive growth in object-oriented design and development. ada95 and its strong ties to dod and government software, and java with an increasing impact on commercial internet-based and general- purpose software, both expand the base of software professionals working on object-oriented platforms. security is a paramount concern in both languages; in ada 95 to manage access to government sensitive data, and in java to control the effects of platform-independent software. organizations will demand high constancy and high assurance in object-oriented software, across a wide range of domains. for example, health care systems need instant access to data in life-critical situations, while cad applications must insure that the most up-to-date specifications on mechanical parts are available in a shared manner to promote cooperation and facilitate productivity. the successful ada 95 tool chest for the year 2000 must contain tools and techniques that support the definition, analyses, and enforcement of security for object-oriented software. this paper investigates security for object-oriented design with a focus on its realization in ada 95. john a. reisner steven a. demurjian
compiling real-time programs into schedulable code  we present a programming language with first-class timing constructs, whose semantics is based on time-constrained relationships between observable events. since a system specification postulates timing relationships between events, realizing the specification in a program becomes a more straightforward process.  using these constraints, as well as those imposed by data and control flow properties, our objective is to transform the code so that its worst-case execution time is consistent with its real-time requirements. to accomplish this goal we first translate an event-based source program into intermediate code, in which the timing constraints are imposed on the code itself, and then use a compilation technique which synthesizes feasible code from the original source program.  seongsoo hong richard gerber
stochastic reliability growth: a model with applications to computer software faults and hardware design faults  an assumption commonly made in early models of software reliability is that the failure rate of a program is a constant multiple of the number of faults remaining. this implies that all faults have the same effect upon the overall failure rate. the assumption is challenged and an alternative proposed. the suggested model results in earlier fault-fixes having a greater effect than later ones (the worst faults show themselves earlier and so are fixed earlier), and the dfr property between fault-fixes (confidence in programs increases during periods of failure-free operations, as well as at fault- fixes). the model shows a high degree of mathematical tractability, and allows a range of reliability measures to be calculated exactly. predictions of total execution time to achieve a target reliability, and total number of fault- fixes to target reliability, are obtained. it is suggested that the model might also find applications in those hardware reliability growth situations where design errors are being eliminated.  b. littlewood
using annotations to reduce dynamic optimization time  _dynamic compilation and optimization are widely used in heterogenous computing environments, in which an intermediate form of the code is compiled to native code during execution. an important trade off exists between the amount of time spent dynamically optimizing the program and the running time of the program. the time to perform dynamic optimizations can cause significant delays during execution and also prohibit performance gains that result from more complex optimization._  _in this research, we present an annotation framework that substantially reduces compilation overhead of java programs. annotations consist of analysis information collected off-line and are incorporated into java programs. the annotations are then used by dynamic compilers to guide optimization. the annotations we present reduce compilation overhead incurred at all stages of compilation and optimization as well as enable complex optimizations to be performed dynamically. on average, our annotation optimizations reduce optimized compilation overhead by 78% and enable speedups of 7% on average for the programs examined._  chandra krintz brad calder
daistish: systematic algebraic testing for oo programs in the presence of side-effects daistish is a tool that performs systematic algebraic testing similar to gannon's daists tool [2]. however, daistish creates effective test drivers for programs in languages that use side effects to implement adts; this includes c++ and most other object-oriented languages. the functional approach of daists does not apply directly in these cases. the approach in our work is most similar to the astoot system of doong and frankl [1]; daistish differs from astoot by using guttag-style algebraic specs (functional notation), by allowing aliasing of type names to tailor the application of parameters in test cases, and by retaining the abilities of daists to compose new test points from existing ones. daistish is a perl script, and is compact and practical to apply. we describe the implementation and our experiments in both eiffel and c++. our work has concentrated on solving the semantics- specific issues of correctly duplicating objects for comparison; we have not worked on methods for selecting specific test cases.daistish consists of a perl script and supporting documentation. the current distribution can be obtained via www at urlhttp://www.cs.unc.edu/~stotts/daistish/ merlin hughes david stotts
a distributed garbage collector for active objects  this paper presents an algorithm that performs garbage collection in distributed systems of active objects (i.e., objects having their own threads of control). our proposition extends the basic marking algorithm proposed by kafura in [1] to a distributed environment. the proposed garbage collector is made up of a set of local garbage collectors, one per site, loosely coupled to a (logically centralized) global garbage collector that maintains a global snapshot of the system state relevant to garbage collection. the specific features of the proposed garbage collector are that local garbage collectors need not be synchronized with each other for detecting garbage objects, and that faulty sites and communication channels are tolerated. the paper describes the proposed garbage collector, together with its implementation and performance for a concurrent object-oriented language running on a local area network of workstations.  isabelle puaut
embedded control systems development with giotto  giotto is a principled, tool-supported design methodology for implementing embedded control systems on platforms of possibly distributed sensors, actuators, cpus, and networks. giotto is based on the principle that time- triggered task invocations plus time-triggered mode switches can form the abstract essence of programming real-time control systems. giotto consists of a programming language with a formal semantics, and a retargetable compiler and runtime library. giotto supports the automation of control system design by strictly separating platform-independent functionality and timing concerns from platform-dependent scheduling and communication issues. the time- triggered predictability of giotto makes it particularly suitable for safety- critical applications with hard real-time constraints. we illustrate the platform- independence and time-triggered execution of giotto by coordinating a heterogeneous flock of intel x86 robots and lego mindstorms robots.  thomas a. henzinger benjamin horowitz christoph meyer kirsch
efficient implementation of the first-fit strategy for dynamic storage allocation  we describe an algorithm that efficiently implements the first-fit strategy for dynamic storage allocation. the algorithm imposes a storage overhead of only one word per allocated block (plus a few percent of the total space used for dynamic storage), and the time required to allocate or free a block is o(log w), where w is the maximum number of words allocated dynamically. the algorithm is faster than many commonly used algorithms, especially when many small blocks are allocated, and has good worst-case behavior. it is relatively easy to implement and could be used internally by an operating system or to provide run-time support for high-level languages such as pascal and ada. a pascal implementation is given in the appendix.  r. p. brent
an apl simulation of feedback systems  practical feedback systems involve interacting linear and nonlinear components. modern techniques of design are based on representing a feedback system by a set of first order nonlinear differential equations and using a digital computer to obtain experimental solutions. in this paper, apl notation is used in a concise development of the mathematical basis of a computing algorithm, and in the realization of an actual system which is effective from the standpoints of ease of use, complexity of feedback systems that can be modeled, and computing efficiency. ease of use is important because a feedback systems engineer is not necessarily skilled in computing and, when using a computer simulation, should be permitted to think in terms of the customary concepts of feedback systems.  wilbur r. lepage richard mcfee
prettyprinting  an algorithm for prettyprinting is given. for an input stream of length n and an output device with linewidth m, the algorithm requires time o(n) and space o(m). the algorithm is described in terms of two parallel processes: the first scans the input stream to determine the space required to print logical blocks of tokens; the second uses this information to decide where to break lines of text; the two processes communicate by means of a buffer of size o(m). the algorithm does not wait for the entire stream to be input, but begins printing as soon as it has received a full line of input. the algorithm is easily implemented.  dereck c. oppen
generation scavenging: a non-disruptive high performance storage reclamation algorithm  many interactive computing environments provide automatic storage reclamation and virtual memory to ease the burden of managing storage. unfortunately, many storage reclamation algorithms impede interaction with distracting pauses. generation scavenging is a reclamation algorithm that has no noticeable pauses, eliminates page faults for transient objects, compacts objects without resorting to indirection, and reclaims circular structures, in one third the time of traditional approaches.  we have incorporated generation scavenging in berkeley smalltalk(bs), our smalltalk-80 implementation, and instrumented it to obtain performance data. we are also designing a microprocessor with hardware support for generation scavenging.  david ungar
complexity measurement of electronic switching system (ess) software  we have been developing a tool that measures the complexity of software: 1) to predict the quality of software products and 2) to allocate proportionally more testing resources to complex modules. the software being measured is real-time and controls telephone switching systems. this software system is large and its development is distributed over a period of several years, with each release providing enhancements and bug fixes.  we have developed a two-stage tool consisting of a parser and an analyzer. the parser operates on the source code and produces operator, operand, and miscellaneous tables. these tables are then processed by an analyzer program that calculates the complexity measures. changes for tuning our halstead counting rules involve simple changes to the analyzer only. during the development there were problems and issues to be confronted dealing with static analysis and code metrics. these are also described in this paper.  in several systems we found that more than 80% of software failures can be traced to only 20% of the modules in the system. the mccabe complexity and some of halstead's metrics score higher than the count of executable statements in their correlations with field failures. it is reasonable to expect that we could devote more effort to the review and test of high- complexity modules and increase the quality of the software product that we send to the field.  david r. gross mary a. king michael r. murr michael r. eddy
describing working environments in opm  in opm, each software process provides a working environment in which programmers can actually work in order to accomplish a designated task, rather than prescribing the algorithm of the task [1], or giving a behavioral description of the task [4]. a process will (i) collect necessary resources, (ii) collect necessary activities, and (iii) specify certain constraint on the execution of activities. a process will also (iv) navigate activities to be performed by a human, (v) execute activities asked by a human, and (vi) execute some activities automatically when certain conditions are met. each working environment may consist of a different set of resources and activities depending on the task to be performed within it. thus the software development environment as a whole will be a collection of smaller and heterogeneous working environments.  in opm, process templates are described in a process programming language called galois [3] which is an extension of c++ [2]. as an example consider the working on bug process illustrated in figure 1. in the working on bug process, a typical edit-compile-run cycle will be performed in order to fix a bug of given source files. figure 2 will give a skeleton of the working on bug process in galois.  yasuhiro sugiyama ellis horowitz
register allocation & spilling via graph coloring  in a previous paper we reported the successful use of graph coloring techniques for doing global register allocation in an experimental pl/i optimizing compiler. when the compiler cannot color the register conflict graph with a number of colors equal to the number of available machine registers, it must add code to spill and reload registers to and from storage. previously the compiler produced spill code whose quality sometimes left much to be desired, and the ad hoe techniques used took considerable amounts of compile time. we have now discovered how to extend the graph coloring approach so that it naturally solves the spilling problem. spill decisions are now made on the basis of the register conflict graph and cost estimates of the value of keeping the result of a computation in a register rather than in storage. this new approach produces better object code and takes much less compile time.  g. j. chaitin
problems in application software maintenance  the problems of application software maintenance in 487 data processing organizations were surveyed. factor analysis resulted in the identification of six problem factors: user knowledge, programmer effectiveness, product quality, programmer time availability, machine requirements, and system reliability. user knowledge accounted for about 60 percent of the common problem variance, providing new evidence of the importance of the user relationship for system success or failure. problems of programmer effectiveness and product quality were greater for older and larger systems and where more effort was spent in corrective maintenance. larger scale data processing environments were significantly associated with greater problems or programmer effectiveness, but with no other problem factor. product quality was seen as a lesser problem when certain productivity techniques were used in development.  bennet p. lientz e. burton swanson
composition of before/after metaclasses in som  in som, the ibm system object model, a class is a run-time object that defines the behavior of its instances by creating an instance method table. because classes are objects, their behavior is defined by other classes (called metaclasses). for example, a "before/after metaclass" can be used to define the implementation of classes that, by suitable construction of their instance method tables, arrange for each invocation of a method to be preceded by execution of a "before method" and followed by execution of an "after method". this paper introduces and solves the problem of composing different before/after metaclasses in the context of som. an enabling element in the solution is som's concept of derived metaclasses, i.e., at run-time a som system derives the appropriate metaclass of a class based on the classes of its parents and an optional metaclass constraint.  ira r. forman scott danforth hari madduri
automatic abstraction for model checking software systems with interrelated numeric constraints model checking techniques have not been effective in important classes of software systems characterized by large (or infinite) input domains with interrelated linear and non-linear constraints over the input variables. various model abstraction techniques have been proposed to address this problem. in this paper, we wish to propose _domain abstraction_ based on data equivalence and trajectory reduction as an alternative and complement to other abstraction techniques. our technique applies the abstraction to the input domain (environment) instead of the model and is applicable to _constraint-free_ and deterministic _constrained_ data transition system. our technique is automatable with some minor restrictions. yunja choi sanjai rayadurgam mats p.e. heimdahl
fast parallel implementation of lazy languages - the equals experience  this paper describes equals, a fast parallel implementation of a lazy functional language on a commercially available shared-memory parallel machine, the sequent symmetry. in contrast to previous implementations, we detect parallelism automatically by propagating exhaustive (normal form) demand. another important difference between equals and previous implementations is the use of reference counting for memory management instead of garbage collection. our implementation shows that reference counting leads to very good scalability, low memory requirements and improved locality. we compare our results with sequntial sml/nj as well as parallel (v, g-machine and gaml implementations.  o. kaser s. pawagi c. r. ramakrishnan i. v. ramakrishnan r. c. sekar
object-oriented design: a responsibility-driven approach  object- oriented programming languages support encapsulation, thereby improving the ability of software to be reused, refined, tested, maintained, and extended. the full benefit of this support can only be realized if encapsulation is maximized during the design process.  we argue that design practices which take a data-driven approach fail to maximize encapsulation because they focus too quickly on the implementation of objects. we propose an alternative object-oriented design method which takes a responsibility-driven approach. we show how such an approach can increase the encapsulation by deferring implementation issues until a later stage.  r. wirfs-brock b. wilkerson
laziness pays! using lazy synchronization mechanisms to improve non-blocking constructions  we present a simple and efficient wait- free implementation of lazy large load-linked/store-conditional (lazy-ll/sc), which can be used to atomically modify a dynamically-determined set of shared variables in a lock-free manner. the semantics of lazy-ll/sc is weaker than that of similar objects used by us previously to design lock-free and wait- free constructions, and as a result can be implemented more efficiently. however, we show that lazy-ll/sc is strong enough to be used in existing non- blocking universal constructions and to build new ones.  mark moir
structured programming in the 1980s  the "structured revolution" is over ten years old. as we enter the 1980s, the major trends growing out of the work on structured program design can be seen. in this paper, the author discusses the major elements of development for the next ten years. among them are: 1. the emergence of the theoretical programmer. 2. structured program design. 3. data structured design. 4. an algebra of logical structures. 5. improvements in programming languages, operating systems, and data base management systems. 6. models and generators.  kenneth t. orr
compiling a functional language  this paper summarizes my experience in implementing a compiler for a functional language. the language is ml(1) [milner 84] and the compiler was first implemented in 1980 as a personal project when i was a postgraduate student at the university of edinburgh(2). at the time, i was familiar with programming language semantics but knew very little about compiler technology; interpreters had been my main programming concern. major influences in the design of this compiler have been [steele 77] [steele 78] and the implementation folklore for statically and dynamically scoped dialects of lisp [allen 78]. as a result, the internal structure of the compiler is fairly unorthodox, if compared for example with [aho 78].  anyway, a compiler for a language like ml has to be different. ml is interactive, statically scoped, strongly typed, polymorphic, and has first class higher- order functions, type inference and dynamic allocation. these features preclude many well-known implementation styles, particularly the ones used for lisp (because of static scoping), the algol family (because of functional values) and c (because of nested scoping and strong typing). the interaction of these features is what gives ml its "character", and makes compilation challenging.  the compiler has been recently partially converted to the new ml standard. the major points of interest which are discussed in this paper are: (a) the interactive interpreter-like usage; (b) the polymorphic type inference algorithm; (c) the compilation of pattern matching; (d) the optimization of the representation of user defined data types; (e) the compilation of functional closures, function application and variable access; (f) the intermediate abstract machine and its formal operational semantics; (g) modules and type-safe separate compilation.  luca cardelli
a semantic model of program faults program faults are artifacts that are widely studied, but there are many aspects of faults that we still do not understand. in addition to the simple fact that one important goal during testing is to cause failures and thereby detect faults, a full understanding of the characteristics of faults is crucial to several research areas in testing. these include fault-based testing, testability, mutation testing, and the comparative evaluation of testing strategies. in this workshop paper, we explore the fundamental nature of faults by looking at the differences between a syntactic and semantic characterization of faults. we offer definitions of these characteristics and explore the differentiation. specifically, we discuss the concept of "size" of program faults --- the measurement of size provides interesting and useful distinctions between the syntactic and semantic characterization of faults. we use the fault size observations to make several predictions about testing and present preliminary data that supports this model. we also use the model to offer explanations about several questions that have intrigued testing researchers. a. jefferson offutt j. huffman hayes