waashk/acm huggingface dataset:
design and verification of secure systems  this paper reviews some of the difficulties that arise in the verification of kernelized secure systems and suggests new techniques for their resolution.  it is proposed that secure systems should be conceived as distributed systems in which security is achieved partly through the physical separation of its individual components and partly through the mediation of trusted functions performed within some of those components. the purpose of a security kernel is simply to allow such a 'distributed' system to actually run within a single processor; policy enforcement is not the concern of a security kernel.  this approach decouples verification of components which perform trusted functions from verification of the security kernel. this latter task may be accomplished by a new verification technique called 'proof of separability' which explicitly addresses the security relevant aspects of interrupt handling and other issues ignored by present methods.  j. m. rushby
how to verify concurrent ada programs: the application of model checking ada 95 is an expressive concurrent programming language with which it is possible to build complex multi-tasking applications. much of the complexity of these applications stem from the interactions between the tasks. this paper argues that model checking tools are now mature enough that they can be used by engineers to verify the logical correctness of their tasking algorithms. the paper illustrates the approach by showing the correctness of an ada implementation of the atomic action protocol. a. burns a. j. wellings
a user interface toolkit based on graphical objects and constraints  one of the most difficult aspects of creating graphical, direct manipulation user interfaces is managing the relationships between the graphical objects on the screen and the application data structures that they represent. coral (constraint-based object-oriented relations and language) is a new user interface toolkit under development that uses efficiently- implemented constraints to support these relationships. using coral, user interface designers can construct interaction techniques such as menus and scroll bars. more importantly, coral makes it easy to construct direct- manipulation user interfaces specialized to particular applications. unlike previous constraint- based toolkits, coral supports defining constraints in the abstract, and then applying them to different object instances. in addition, it provides iteration constructs where lists of items (such as those used in menus) can be constrained as a group. coral has two interfaces: a declarative interface that provides a convenient way to specify the desired constraints, and a procedural interface that will allow a graphical user interface management system (uims) to automatically create coral calls.  pedro szekely brad myers
software error analysis: a real case study involving real faults and mutations the paper reports on a first experimental comparison of software errors generated by real faults and by 1st-order mutations. the experiments were conducted on a program developed by a student from the industrial specification of a critical software from the civil nuclear field. emphasis was put on the analysis of errors produced upon activation of 12 real faults by focusing on the mechanisms of error creation, masking, and propagation up to failure occurrence, and on the comparison of these errors with those created by 24 mutations. the results involve a total of 3730 errors recorded from program execution traces: 1458 errors were produced by the real faults, and the 2272 others by the mutations. they are in favor of a suitable consistency between errors generated by mutations and by real faults: 85% of the 2272 errors due to the mutations were also produced by the real faults. moreover, it was observed that although the studied mutations were simple faults, they can create erroneous behaviors as complex as those identified for the real faults. this lends support to the representativeness of errors due to mutations. murial daran pascale thevenod-fosse
linearity and the pi-calculus  the economy and flexibility of the pi- calculus make it an attractive object of theoretical study and a clean basis for concurrent language design and implementation. however, such generality has a cost: encoding higher-level features like functional computation in pi- calculus throws away potentially useful information. we show how a linear type system can be used to recover important static information about a process's behavior. in particular, we can guarantee that two processes communicating over a linear channel cannot interfere with other communicating processes. after developing standard results such as soundness of typing, we focus on equivalences, adapting the standard notion of barbed bisimulation to the linear setting and showing how reductions on linear channels induce a useful "partial confluence" of process behaviors. for an extended example of the theory, we prove the validity of a tail-call optimization for higher-order functions represented as processes.  naoki kobayashi benjamin c. pierce david n. turner
model like an egyptian  when the ancient egyptians built the pyramids, they built them with a strong sturdy base, and then added layers in gradually smaller increments until the top came to a point. we visit these monuments today and marvel at their architectural ingenuity. imagine---they had advanced to such a stage, that they were able to determine that the pyramids would stand a lot longer if they were built with the point at the top, instead of at the bottom. why hasn't the software development community been able to achieve this same level of advancement?  one of the big questions facing many software organizations today is choosing between object-oriented or structured analysis as the method for analyzing requirements. while many make this choice based on being trendy, or building on past experience, etc., they fail to realize that the result of their choice may be the equivalent of building an upside-down pyramid. the key to making the right choice is based on an in-depth understanding of the patterns that exist in the designs of systems in specific application groups. our experience applying the practical ada design method (padadm) across a variety of applications has identified that communication systems, database systems, and control systems have distinguishing patterns in how they aggregate ada design objects. when analyzing the requirements for these systems, knowledge of these patterns is fundamental for choosing an analysis method that aggregates its information in ways that map to those of the final design.  all systems will contain a mixture of data (object), process (function), and state (behavior) characteristics, but certain analysis methods choose one of these characteristics as its base, and then build the rest on top. if your system characteristics aren't distributed with the same percentages as the method expects, you're building an upside-down pyramid. so, lets stop choosing the trendiest method, and look for the one that lets us model like the egyptians!  michael i. frankel
modeling industrial embedded systems with uml  the main purpose of this paper is to present how the unified modeling language (uml) can be used for modeling industrial embedded systems. by using a car radios production line as a running example, the paper demonstrates the modeling process that can be followed during the analysis phase of complex control applications. in order to guarantee the continuity mapping of the models, the authors propose some guidelines to transform the use case diagrams into a single object diagram, which is one of the main diagrams for the next development phases.  joão m. fernandes ricardo j. machado henrique d. santos
team: a support environment for testing, evaluation, and analysis  current research indicates that software reliability needs to be achieved through the careful integration of a number of diverse testing and analysis techniques. to address this need, the team environment has been designed to support the integration of and experimentation with an ever growing number of software testing and analysis tools. to achieve this flexibility, we exploit three design principles: component technology so that common underlying functionality is recognized; generic realizations so that these common functions can be instantiated as diversely as possible; and language independence so that tools can work on multiple languages, even allowing some tools to be applicable to different phases of the software lifecycle. the result is an environment that contains building blocks for easily constructing and experimenting with new testing and analysis techniques. although the first prototype has just recently been implemented, we feel it demonstrates how modularity, genericity, and language independence further extensibility and integration.  lori a. clarke debra j. richardson steven j. zeil
building tcl-tk guis for hrt-hood systems this work explores tcl-tk 8.0 as a building tool for script-based guis in ada95 real-time systems. tcl-tk 8.0 is a library that makes graphic programming easier, but it suffers from being non-thread-safe. an application architecture is proposed, the deferred server, which provides transparent use of tcl-tk to multithreaded ada95 applications via tash, a thick binding that allows ada95 single-threaded code to use tcl- tk. we find that only a minimal extension to tcl-tk 8.0 and tash is required to support it, while a successful prototype has been implemented based on these ideas. likewise, the early integration of tcl-tk graphic user interfaces in hrt-hood designs is examined; unfortunately, in this respect, we conclude that this is not feasible. however, a hrt-hood conform distributed configuration is outlined in wich the user interface becomes a multithreaded remote service based on the deferred server architecture. juan carlos diaz martin isidro irala veloso jose manuel rodriguez garcia
optimal mutex policy in ada 95 priority inversion is any situation where low priority tasks are served before higher priority tasks. it is recognized as a serious problem for real-time systems. in this paper, we present some of the important features of the real-time annex of ada 95. we also implement the _optimal mutex policy (omp)_ in ada 95 to better illustrate ada's new usefulness for real-time programming. a detailed discussion of this protocol and other related issues are presented. jim abu-ras
a simple software environment based on objects and relations  this paper presents a simple programming system based on a clear separation of value-oriented programming and object-oriented programming [maclennan82, maclennan83a]. the value-oriented component is a conventional functional programming language. the object-oriented component is based on a model of objects and values connected by relations, and on production system-like rules that determine the alteration of these relations through time. it is shown that these few basic ideas permit simple prototyping of a software development environment.  bruce j. maclennan
high performance parallel and distributed computation in compositional cc++ c++ was designed to support a wide range of programming styles. a parallel extension to c++ should support parallelism in all the different programming styles that a c++ program might exploit as well as support a broad range of parallel programming paradigms, such as message passing, active objects and shared memory concurrency. compositional c++ (cc++) is a parallel c++ that was designed with these goals in mind. in this article, we motivate the design of cc++ and provide a brief overview of the language. we will illustrate how cc++ can be used to define a reusable parallel paradigm libraries and describe how one parallel application used cc++ language features to combine different types of parallelism in a single application. carl kesselman
from programming environments to environments for designing  though there have been advances in end-user programming, complex applications still need professional developers. this inspired look at the future of creating complex software explores the shift from programming environments to design environments, discussing environments that help developers satisfy end- users' cognitive needs and help deal with contextual issues such as the aesthetic, practical, and social properties of the application and the users. a strong case is made that design environments will need to provide robust support for communication between developers and end users.  terry winograd
efficient implementation of java interfaces: invokeinterface considered harmless single superclass inheritance enables simple and efficient table- driven virtual method dispathc. however, virtual method table dispatch does not handle multiple inheritance and interfaces. this complication has led to a widespread misimpression that interface method dispatch is inherently inefficient. this paper argues that with proper implementation techniques, java interfaces need _not_ be a source of significant performance degradation. bowen alpern anthony cocchi stephen fink david grove
a graphical tool for driving the parallel computation of pseudosprectra  this paper presents the programming environment of a new tool for the parallel computation of pseudospectra. based on the ppa talgorithm described in [16, 17], this algorithm offers total reliability and can handle singularities along the level curve without difficulty. it offers a guarantee of termination even in the presence of round-off errors and makes use of the large granularity for parallelism in pat [17]. this results in large speedups and high efficiency. the software is able to trace multiple level curves simultaneously and task in to account the symmetry of the pseudospectrum in the case of real matrices to reduce the total computational cost. the ability of the software to compute multiple slices of the same level curve simultaneously enhances the speedup and efficiency. the user drives the parallel application through a graphical user interface. the interface includes graphical features (zoom in, zoom out, color control,…) and computational features (raise or lower level curve priority, limit computation to a set of processors,…) crucial for the appreciation of the information provided by the pseudospectrum. although the application was developed for the computation of the pseudospectrum, it can be used, provided minor modifications, to trace the level curves of any continuous, not necessarily smooth, function _f_(_z_): c -&gt; r  dany mezher
an empirical study of regression test selection techniques  regression testing is the process of validating modified software to detect whether new errors have been introduced into previously tested code and to provide confidence that modifications are correct. since regression testing is an expensive process, researchers have proposed regression test selection techniques as a way to reduce some of this expense. these techniques attempt to reduce costs by selecting and running only a subset of the test cases in a program's existing test suite. although there have been some analytical and empirical evaluations of individual techniques, to our knowledge only one comparative study, focusing on one aspect of two of these techniques, has been reported in the literature. we conducted an experiment to examine the relative costs and benefits of several regression test selection techniques. the experiment examined five techniques for reusing test cases, focusing on their relative ablilities to reduce regression testing effort and uncover faults in modified programs. our results highlight several differences between the techiques, and expose essential trade-offs that should be considered when choosing a technique for practical application.  todd l. graves mary jean harrold jung-min kim adam porter gregg rothermel
software testing and analysis of object-oriented software our work has studied new language mechanisms for accessing message invocations in message passing based concurrent programming languages. invocation handling mechanisms in many concurrent languages have significant limitations that make it difficult or costly to solve common programming situations encountered in program visualization, debugging, and scheduling scenarios. we have defined and implemented new such mechanisms within the sr concurrent language and have gained some experience with them.this work has led us to want a cleaner, higher-level way of defining mechanisms for message invocation. we are, therefore, now taking an object-oriented approach. as a step toward that goal, we are currently applying our ideas to java.below, we briefly summarize these two areas. jeff offutt
treat - an applicative code generator  treat is a special purpose language for use in compiler writing. a treat program translates a graph into c-trees (the intermediate language of the pcc compiler) and uses the back end of the c compiler to generate code. treat has been developed specifically for use in an adatm compiler. a treat program consists of applicative transformation rules. treat's distinctive aspects include triggering transformations during pattern matching, a context mechanism for dynamic binding and assignment in a language with lazy evaluation.  jerald s. schwarz dean rubine
using model checking to generate tests from requirements specifications  recently, many formal methods, such as the scr (software cost reduction) requirements method, have been proposed for improving the quality of software specifications. although improved specifications are valuable, the ultimate objective of software development is to produce software that satisfies its requirements. to evaluate the correctness of a software implementation, one can apply black-box testing to determine whether the implementation, given a sequence of system inputs, produces the correct system outputs. this paper describes a specification-based method for constructing a suite of test sequences, where a test sequence is a sequence of inputs and outputs for testing a software implementation. the test sequences are derived from a tabular scr requirements specification containing diverse data types, i.e., integer, boolean, and enumerated types. from the functions defined in the scr specification, the method forms a collection of predicates called branches, which "cover" all possible software behaviors described by the specification. based on these predicates, the method then derives a suite of test sequences by using a model checker's ability to construct counterexamples. the paper presents the results of applying our method to four specifications, including a sizable component of a contractor specification of a real system.  angelo gargantini constance heitmeyer
beyond induction variables: detecting and classifying sequences using a demand-driven ssa form  linear induction variable detection is usually associated with the strength reduction optimization. for restructuring compilers, effective data dependence analysis requires that the compiler detect and accurately describe linear and nonlinear induction variables as well as more general sequences. in this article we present a practical technique for detecting a broader class of linear induction variables than is usually recognized, as well as several other sequence forms, including periodic, polynomial, geometric, monotonic, and wrap-around variables. our method is based on factored use-def (fud) chains, a demand-driven representation of the popular static single assignment (ssa) form. in this form, strongly connected components of the associated ssa graph correspond to sequences in the source program: we describe a simple yet efficient algorithm for detecting and classifying these sequences. we have implemented this algorithm in nascent, our restructuring fortran 90+ compiler, and we present some results showing the effectiveness of our approach.  michael p. gerlek eric stoltz michael wolfe
incremental compilation of optimized code  although optimizing compilers have successfully been used to reduce the size and running times of compiled programs, present incremental compilers only support the incremental update of unoptimized code. in this work, we extend the notion of incremental compilation to include optimized code. techniques to incrementally compile locally optimized code, given intermediate code modifications are developed using a program representation based on flow graphs and dags. a model is designed to represent both unoptimized and optimized code and to maintain an optimizing history. changes to the optimized code which either destroy optimizations or create conditions for further optimizations are incorporated into the model and the optimized code without recompiling unaffected optimizations.  lori l. pollock mary lou soffa
zero-cost range splitting  this paper presents a new optimization technique that uses empty delay slots to improve code scheduling. we are able to split live ranges for free, by inserting spill code into empty delay slots. splitting a live range can reduce interferences with other live ranges and can sometimes free registers. live ranges no longer interfering with the split live range can sometimes make use of the extra register.  our algorithm, as a final pass over the code, exploits empty delay slots that would remain unused if spill code was not inserted. this paper proposes a variety of optimizations that use the extra registers generated from live range splitting, including coalescing live ranges and improving code scheduling. we present an algorithm for improving code scheduling and present implementation results.  steven m. kurlander charles n. fischer
analyzing the test process using structural coverage  a large, commercially developed fortran program was modified to produce structural coverage metrics. the modified program was executed on a set of functionally generated acceptance tests and a large sample of operational usage cases. the resulting structural coverage metrics are combined with fault and error data to evaluate structural coverage in the sel environment.  we can show that in this environment the functionally generated tests seem to be a good approximation of operational use. the relative proportions of the exercised statement sub-classes (executable, assignment, call, do, if, read, write) changes as the structural coverage of the program increases. we also propose a method for evaluating if two sets of input data exercise a program in a similar manner.  we also provide evidence that implies that in this environment, faults revealed in a procedure are independent of the number of times the procedure is executed and that it may be reasonable to use procedure coverage in software models that use statement coverage. finally, the evidence suggests that it may be possible to use structural coverage to aid in the management of the acceptance test process.  james ramsey victor r. basili
parallel and distributed incremental attribute evaluation algorithms for multiuser software development environments  the problem of change propagation in multiuser software development environments distributed across a local-area network is addressed. the program is modeled as an attributed parse tree segmented among multiple user processes and changes are modeled as subtree replacements requested asynchronously by individual users. change propagation is then implemented using decentralized incremental evaluation of an attribute grammar that defines the static semantic properties of the programming language. building up to our primary result, we first present algorithms that support parallel evaluation on a centralized tree in response to single edits using a singe editing cursor and multiple edits with multiple editing cursors. then we present our algorithm for parallel evaluation on a decentralized tree. we also present a protocol to guarantee reliability of the evaluation algorithm as components of the decentralized tree become unavailable due to failures and return to availability.  gail e. kaiser simon m. kaplan