Undergraduate students at Michigan State University (MSU) have offered Spartan Girls Who Code (SGWC) clubs on the MSU campus for three spring semesters. Marketed to 6th-12th graders who identify as female, SGWC aims to (1) introduce participants to the fundamentals of computing, (2) contextualize computing in modern life, (3) improve participants' confidence and attitudes toward computing, and (4) foster an inclusive, supportive, and welcoming learning environment. Toward these ends, MSU students serve as near-peer mentors, guiding participants in active learning, collaborative learning, project-based learning and culturally-relevant computing activities. Due to the COVID-19 pandemic, SGWC was forced to abruptly transition to virtual meetings after the first five in-person meetings of the spring 2020 session. Club attendance fell in the immediate wake of Michigan public school closures by about 50%. But retention and morale of those who attended the first virtual session was high. Moreover, feedback from those who completed SGWC and their parents indicate overall satisfaction with the virtual adaptation of SGWC and support that it was successful in achieving its goals. This paper highlights lessons distilled over the course of SGWC's transition to a virtual format. Our goal is to provide a vision for the post-pandemic role of out-of-school time coding clubs in the diversification and development of future computer scientists.

Recently, many computing departments in universities and colleges around the nation have seen increases in enrollments in the major. While these increases are largely welcome, it is important that the student population be diversified even as enrollments swell. What are departments doing to ensure that women are both recruited and retained in this changing environment? This panel will share interventions undertaken by three U.S. post-secondary institutions that have focused on increasing their female and underrepresented student enrollment. Their efforts all include multi-pronged approaches, which is consistent with the social science research on how to create institutional reform in academic departments [1]. These institutions have made changes that reflect increased departmental engagement with recruitment and retention for diversity: a shift in individual faculty pedagogical strategies, introductory course restructuring, as well as more outreach and preparatory programs for incoming students. These departments have not only implemented existing evidence-based practices to make these lasting changes, but have tried new ideas as well.

As a bridge from informal business requirements to precise specifications, conceptual models serve a critical role in the development of enterprise systems. Instantiating conceptual models with test data can help stakeholders validate the model and provide developers with a test database to validate their code. ORM is a popular conceptual modeling language due in part to its expressive constraint language. Due to that expressiveness, instantiating an arbitrary ORM model is NP-hard. Smaragdakis et al. identified a subset of ORM called ORM− that can be instantiated in polynomial time. However, ORM− excludes several constraints commonly used in commercial models. Recent research has extended ORM− through semantics-preserving transformations. We extend the set of ORM models that can be transformed to ORM− models by using a class of non-semantics-preserving transformations called constraint strengthening. We formalize our approach as a special case of Stevens’ model transformation framework. We discuss an example transformation and its limitations, and we conclude with a proposal for future research.

Conceptual data models describe information systems without the burden of implementation details, and are increasingly used to generate code. They could also be analyzed for consistency and to generate test data except that the expressive constraints supported by popular modeling notations make such analysis intractable. In an earlier empirical study of conceptual models created at LogicBlox Inc., Smaragdakis, Csallner, and Subramanian found that a restricted subset of ORM, called ORM−, includes the vast majority of constraints used in practice and, moreover, allows scalable analysis. After that study, however, LogicBlox Inc. obtained a new ORM modeling tool, which supports discovery and specification of more complex constraints than the previous tool. We report findings of a follow-up study of models constructed using the more powerful tool. Our study finds that LogicBlox developers increasingly rely on a small number of features not in the ORM− subset. We extend ORM− with support for two of them: objectification and a restricted class of external uniqueness constraints. The extensions significantly improve our ability to analyze the ORM models created by developers using the new tool. We also show that a recent change to ORM has rendered the original ORM− algorithms unsound, in general; but that an efficient test suffices to show that these algorithms are in fact sound for the ORM− constraints appearing in any of the models currently in use at LogicBlox.

Concurrent software is notoriously difficult to debug. We investigate the use of UML sequence diagrams to help developers correctly reason about the potential behaviors of buggy concurrent software. We conducted a controlled experiment that compared internal (i.e., "in the head") and external representations for reasoning about multithreaded software. For external representations, participants created multithreaded sequence diagrams. The results of the experiment demonstrate a strong positive effect associated with using external representations. Participants who drew diagrams were significantly more successful at reasoning about the potential behavior of concurrent software. Moreover, participants who produced diagrams with higher levels of detail and with fewer errors tended to achieve greater levels of success. Additionally, this paper contributes an extension to the UML sequence diagram notation for showing behavior of multithreaded software and formal metrics for assessing the complexity of thread interactions.

We describe a framework, called the synchronization policy prototyper (SyPP), for generating tools to aid in assessing the appropriateness of strictly exclusive synchronization policies under expected program usage scenarios. A SyPP tool aims to help during evolution of an existing program when the synchronization policy that it implements needs to be changed.

Empirical studies are important for understanding how well current design methods and notations support development of multi-threaded programs. Unfortunately, concurrency exacerbates an already difficult problem in drawing conclusions from such studies: How to objectively measure the quality of candidate solutions produced by participants in the studies. This paper explores the use of formal modeling and analysis for this purpose. We describe initial findings of a small pilot study to determine if we can objectively differentiate sample candidate solutions with respect to their use of synchronization primitives. To do so, we faithfully model these candidate solutions and various synchronization-related properties in the Finite State Processes (FSP) notation and use the Labeled Transition System Analyzer (LTSA) to analyze the solution models against the properties.

Graduates of computer science degree programs are increasingly being asked to maintain large, multi-threaded software systems; however, the maintenance of such systems is typically not well-covered by software engineering texts or curricula. We conducted a think-aloud study with 15 students in a graduate-level computer science class to discover the strategies that students apply, and to what effect, in performing corrective maintenance on concurrent software. We collected think-aloud and action protocols, and annotated the protocols for a number of behavioral attributes and maintenance strategies. We divided the protocols into groups based on the success of the participant in both diagnosing and correcting the failure. We evaluated these groups for statistically significant differences in these attributes and strategies.

While the sources of complexity in the initial design and verification of multi-threaded software systems are well-documented, less is known of the issues specific to the maintenance of these systems. The literature contains a number of observational studies of programmers performing maintenance, conducted in the context of sequential software and designed to investigate the factors and behaviors that lead to success. To help fill the gap in knowledge in the area of concurrent software maintenance, we conducted a study that refines the findings of two prior studies, those of Littman et al. and of Vessey, to address issues and obstacles that arise in the understanding of concurrent software. We validated these refinements by observing programmers performing corrective maintenance on a small but complex multi-threaded server program.

This paper explores an approach to design for verification in systems built atop a middleware framework which separates synchronization concerns from the "core-functional logic" of a program. The framework is based on a language-independent compositional model of synchronization contracts, called Szumo, which integrates well with popular OO design artifacts and provides strong guarantees of non-interference for a class of strictly exclusive systems. An approach for extracting models from Szumo design artifacts and analyzing the generated models to detect deadlocks is described. A key decision was to use Constraint Handling Rules to express the semantics of synchronization contracts, which allowed a transparent model of the implementation logic.

It is widely held that programming language extensions that support separation of concerns and that are also integrative benefit development, maintenance and reuse of software designs and code. Such is the intent of our synchronization units model (Szumo), which unifies new features for expressing synchronization in a multi-threaded program with existing features of an object-oriented language. However, to make effective use of a language extension, a programmer needs an accurate mental model of how new concepts affect and are affected by existing concepts. Moreover, good separation dictates that interactions between these concepts should be understandable at the level of the new concepts. This suggests that the semantics of Szumo should be specifiable as a self-contained partial specification, called a view, and the semantics of its integration with other language features should be specifiable by view composition. To our knowledge, however, view-based approaches have not been applied in specifying the semantics of language extensions. Moreover, devising separable views that serve to simplify comprehensibility of a complex specification is still more of an art than a science. This paper presents a case study in the use of views in structuring a Z specification of Szumo

The safe and reliable use of concurrency in multi-threaded systems has emerged as a fundamental engineering concern. We recently developed a model of synchronization contracts to address this concern in programs written in object-oriented languages. Programs written using our model comprise modules that declare access requirements in module interfaces in lieu of using low-level synchronization primitives in module implementations. At run time, these contracts are negotiated to derive schedules that guarantee freedom from data races while avoiding a large class of deadlock situations

Amalia is a generator framework for constructing analyzers for operationally defined formal notations. These generated analyzers are components that are designed for customization and integration into a larger environment. The customizability, and efficiency of Amalia analyzers owe to a computational structure called an inference graph. This paper describes this structure, how inference graphs enable Amalia to generate analyzers for operational specifications, and how we build in assurance. On another level, this paper illustrates how to balance the need for assurance, which typically implies a formal proof obligation, against other design concerns, whose solutions leverage design techniques that are not (yet) accompanied by mature proof methods. We require Amalia-generated designs to be transparent with respect to the formal semantic models upon which they are based. Inference graphs are complex structures that incorporate many design optimizations. While not formally verifiable, their fidelity with respect to a formal operational semantics can be discharged by inspection.

The Amalia framework generates lightweight components that automate the analysis of operational specifications and designs. A key concept is the step analyzer, which enables Amalia to automatically tailor high-level analyses, such as behavior simulation and model checking, to different specification languages and representations. A step analyzer uses a new abstraction, called an inference graph, for the analysis. It creates and evaluates an inference graph on-the-fly during a top-down traversal of a specification to deduce the specification's local behaviors (called steps). The nodes of an inference graph directly reify the rules in an operational semantics, enabling Amalia to automatically generate a step analyzer from an operational description of a notation's semantics. Inference graphs are a clean abstraction that can be formally defined. The paper provides a detailed but informal introduction to inference graphs. It uses example specifications written in LOTOS for purposes of illustration.

Automatic-verification capability tends to be packaged into stand-alone tools, as opposed to components that are easily integrated into a larger software-development environment. Such packaging complicates integration because it involves translating internal representations into a form compatible with the stand-alone tool. By contrast, lightweight-analysis components package analysis capability in a form that does not involve such a translation. Borrowing ideas from GenVoca and object-oriented design patterns, we developed a domain model and an automatic generation framework for lightweight-analysis components. The generated components operate directly over the internal form of a specification without requiring a change in representation. Moreover, the domain model identifies several "useful subsets" that can be used to customize analysis capability to a particular application. We validated this domain model by generating lightweight analyzers for temporal logic and the behavioral subset of Lotos.

Article Analysis of a scheduler for a CAD framework Share on Authors: David S. Keyes Picker International, Inc. World Headquarters, 595 Miner Road, Cleveland, OH Picker International, Inc. World Headquarters, 595 Miner Road, Cleveland, OHView Profile , Laura K. Dillon Department of Computer Science & Engineering, 3115 Engineering Building, Michigan State University, East Lansing, MI Department of Computer Science & Engineering, 3115 Engineering Building, Michigan State University, East Lansing, MIView Profile , Moon Jung Chung Department of Computer Science & Engineering, 3115 Engineering Building, Michigan State University, East Lansing, MI Department of Computer Science & Engineering, 3115 Engineering Building, Michigan State University, East Lansing, MIView Profile Authors Info & Claims ICSE '99: Proceedings of the 21st international conference on Software engineeringMay 1999 Pages 152–161https://doi.org/10.1145/302405.302461Online:16 May 1999Publication History 2citation192DownloadsMetricsTotal Citations2Total Downloads192Last 12 Months3Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Most analysis methods for real-time systems assume that all the components of the system are at roughly the same stage of development and can be expressed in a single notation, such as a specification or programming language. There are, however, many situations in which developers would benefit from tools that could analyze partially-implemented systems: those for which some components are given only as high-level specifications while others are fully implemented in a programming language. In this paper, we propose a method for analyzing such partially-implemented real-time systems. We consider real-time concurrent systems for which some components are implemented in Ada and some are partially specified using regular expressions and graphical interval logic (GIL), a real-time temporal logic. We show how to construct models of the partially-implemented systems that account for such properties as run-time overhead and scheduling of processes, yet support tractable analysis of nontrivial programs. The approach can be fully automated, and we illustrate it by analyzing a small example.

Pharos is a .sca&zbledistributed architecture for locating heterogeneous informatdon sources.!7he system incorporates a hierarcfiical metaduta structure into a multi-level rettieval system.Queries are resolved through an iterative decisionmaking process.The first step retrieves coarse-grain metadata, about all sources, stored on iocal, mastively replicated, high-level servers.Further steps retrieve more detailed matadata, about a greatly reduced set of souwes, stored on remote, sparsety replicated, topic-based mid-level servers.We present results of a simulation which indicate the feasibility of the architecture.We describe the structure, distribution, and retrieval of the metadata in Pharos to enable users to locate desirable information soumes over the Internet.

We propose a method for analyzing partially-implemented real-time systems.Here we consider real-time concurrent systems for which some components are implemented in Ada and some are partially specified using regular expressions and Graphical Interval Logic (GIL), a real-time temporal logic.We show how to construct models of the partiallyimplemented systems that account for such properties as run-time overhead and scheduling of processes, yet support tractable analysis of nontrivial programs.The approach can be fully automated, and we illustrate it by analyzing a small example.

This article analyzes the semantics of task dependence and termination in Ada. We use a contour model of Ada tasking in examining the implications of and possible motivation for the rules that determine when procedures and tasks terminate during execution of an Ada program. The termination rules prevent the data that belong to run-time instances of scope units from being deallocated prematurely, but they are unnecessarily conservative in this regard. For task instances that are created by invoking a storage allocator, we show that the conservative termination policy allows heap storage to be managed more efficiently than a less conservative policy. The article also examines the manner in which the termination rules affect the synchronization of concurrent tasks. Master-slave and client-server applications are considered. We show that the rules for distributed termination of concurrent tasks guarantee that a task terminates only if it can no longer affect the outcome of an execution. The article is meant to give programmers a better understanding of Ada tasking and to help language designers assess the strengths and weaknesses of the termination model.

Concurrent real-time systems are among the most difficult systems to design because of the many possible interleavings of events and because of the timing requirements that must be satisfied. We have developed a graphical environment based on Real-Time Graphical Interval Logic (RTGIL) for specifying and reasoning about the designs of concurrent real-time systems. Specifications in the logic have an intuitive graphical representation that resembles the timing diagrams drawn by software and hardware engineers, with real-time constraints that bound the durations of intervals. The syntax-directed editor of the RTGIL environment enables the user to compose and edit graphical formulas on a workstation display; the automated theorem prover mechanically checks the validity of proofs in the logic; and the database and proof manager tracks proof dependencies and allows formulas to be stored and retrieved. This article describes the logic, methodology, and tools that comprise the prototype RTGIL environment and illustrates the use of the environment with an example application.

This paper describes a generic tableau algorithm, which is the basis for a general customizable method for producing oracles from temporal logic specifications. A generic argument gives semantic rules with which to build the semantic tableau for a specification. Parameterizing the tableau algorithm by semantic rules permits it to easily accommodate a variety of temporal operators and provides a clean mechanism for fine-tuning the algorithm to produce efficient oracles.The paper develops conditions to ensure that a set of rules results in a correct tableau procedure. It gives sample rules for a variety of linear-time temporal operators and shows how rules are tailored to reduce the size of an oracle.

Interval logic has been introduced as a temporal logic that provides higher-level constructs and an intuitive graphical representation, making it easier in interval logic than in other temporal logics to specify and reason about concurrency in software and hardware designs. In this paper we present axiomatizations for two propositional interval logics and relate these logics to Until Temporal Logic. All of these logics are discrete linear-time temporal logics with no next operator. The next operator obstructs the use of hierarchical abstraction and refinement, and makes reasoning about concurrency difficult.

Verifying that test executions are correct is a crucial step in the testing process. Unfortunately, it can be a very arduous and error-prone step, especially when testing a concurrent system. System developers can therefore benefit from oracles automating the verification of test executions.This paper examines the use of Graphical Interval Logic (GIL) for specifying temporal properties of concurrent systems and describes a method for constructing oracles from GIL specifications. The visually intuitive representation of GIL specifications makes them easier to develop and to understand than specifications written in more traditional temporal logics.Additionally, when a test execution violates a GIL specification, the associated oracle provides information about a fault. This information can be displayed visually, together with the execution, to help the system developer see where in the execution a fault was detected and the nature of the fault.

This article describes a graphical interval logic that is the foundation of a tool set supporting formal specification and verification of concurrent software systems. Experience has shown that most software engineers find standard temporal logics difficult to understand and use. The objective of this article is to enable software engineers to specify and reason about temporal properties of concurrent systems more easily by providing them with a logic that has an intuitive graphical representation and with tools that support its use. To illustrate the use of the graphical logic, the article provides some specifications for an elevator system and proves several properties of the specifications. The article also describes the tool set and the implementation.

The successful development of complex real-time systems depends on analysis techniques that can accurately assess the timing properties of those systems. This paper describes a technique for deriving upper and lower bounds on the time that can elapse between two given events in an execution of a concurrent software system running on a single processor under arbitrary scheduling. The technique involves generating linear inequalities expressing conditions that must be satisfied by all executions of such a system and using integer programming methods to find appropriate solutions to the inequalities. The technique does not require construction of the state space of the system and its feasibility has been demonstrated by using an extended version of the constrained expression toolset to analyze the timing properties of some concurrent systems with very large state spaces.>

Real-Time Future Interval Logic (RTFIL) is a visual logic with formulae that resemble timing diagrams. It is a dense real-time temporal logic that is based on two simple temporal primitives: interval modalities for the purely qualitative part and duration predicates for the quantitative part. We present the logic, and illustrate its use in specifying the railroad crossing example and in proving some of its properties. The logic is decidable by reduction to the emptiness problem of Timed Buchi Automata. An automated theorem prover based on this decision procedure has been implemented as part of a graphical proof environment. The proofs of the railroad crossing example have been verified using this theorem prover. An automated theorem prover and a graphical specification language greatly facilitate the task of verifying real-time proofs. This convenience apart, RTFIL is invariant under real-time stuttering and does not admit instantaneous states. These properties facilitate proof methods based on abstraction and refinement.>

A visual execution model for Ada tasking can help programmers attain a deeper understanding of the tasking semantics. It can illustrate subtleties in semantic definitions that are not apparent in natural language design. We describe a contour model of Ada tasking that depicts asynchronous tasks (threads of control), relationships between the environments in which tasks execute, and the manner in which tasks interact. The use of this high-level execution model makes it possible to see what happens during execution of a program. The paper provides an introduction to the contour model of Ada tasking and demonstrates its use.

We present a description of a graphical interval logic that is the foundation of a toolset we are developing to support formal specification and verification of concurrent software systems. Experience has shown that most software engineers find standard temporal logics difficult to under- stand and to use. Our objective is to enable software engineers to specify and reason about temporal properties of concurrent systems more easily by providing them with a logic that has an intuitive graphical representation and with tools that support its use. To illustrate the use of our graphical interval logic, we provide a specification for a readers/writers database system and prove several properties of the specification.

The constrained expression approach to analysis of concurrent software systems can be used with a variety of design and programming languages and does not require a complete enumeration of the set of reachable states of the concurrent system. The construction of a toolset automating the main constrained expression analysis techniques and the results of experiments with that toolset are reported. The toolset is capable of carrying out completely automated analyses of a variety of concurrent systems, starting from source code in an Ada-like design language and producing system traces displaying the properties represented bv the analysts queries. The strengths and weaknesses of the toolset and the approach are assessed on both theoretical and empirical grounds.>

A method is presented for using symbolic execution to generate the verification conditions required for proving correctness of programs written in a tasking subset of Ada. The symbolic execution rules are derived from proof systems that allow tasks to be verified independently in local proofs, which are then checked for cooperation. The isolation nature of this approach to symbolic execution of concurrent programs makes it better suited to formal verification than the more traditional interleaving approach, which suffers from combinatorial problems. The criteria for correct operation of a concurrent program include partial correctness, as well as more general safety properties, such as mutual exclusion and freedom from deadlock.

The isolation approach to symbolic execution of Ada tasking programs provides a basis for automating partial correctness proofs. The strength of this approach lies in its isolation nature; tasks are symbolically executed and verified independently, and then checked for cooperation where interference can occur. This keeps the verification task computationally feasible and enhances its compositionality. Safety, however, is a more appropriate notion of correctness for concurrent programs than partial correctness. The author shows how the isolation approach to symbolic execution of Ada tasking program supports the verification of general safety properties. Specific safety properties that are considered include mutual exclusion, freedom from deadlock, and absence of communication failure. The techniques are illustrated using a solution to the readers and writers problem.>

It is extremely difficult to characterize the possible behaviors of a distributed software system through informal reasoning. Developers of distributed systems require tools that support formal reasoning about properties of the behaviors of their systems. These tools should be applicable to designs and other preimplementation descriptions of a system, as well as to completed programs. Furthermore, they should not limit a developer's choice of development languages. In this paper we present a basis for broadly applicable analysis methods for distributed software systems. The constrained expression formalism can be used with a wide variety of distributed system development notations to give a uniform closed-form representation of a system's behavior. A collection of formal analysis techniques can then be applied with this representation to establish properties of the system. Examples of these formal analysis techniques appear elsewhere. Here we illustrate the broad applicability of the constrained expression formalism by showing how constrained expression representations are obtained from descriptions of systems in three different notations: SDYMOL, CSP, and Petri nets. Features of these three notations span most of the significant alternatives for describing distributed software systems. Our examples thus offer persuasive evidence for the broad applicability of the constrained expression approach.

An approach to the design of concurrent software systems based on the constrained expression formalism is described. This formalism provides a rigorous conceptual model for the semantics of concurrent computations, thereby supporting analysis of important system properties as part of the design process. This approach allows designers to use standard specification and design languages, rather than forcing them to deal with the formal model explicitly or directly. As a result, the approach attains the benefits of formal rigor without the associated pain of unnatural concepts or notations for its users. The conceptual model of concurrency underlying the constrained expression formalism treats the collection of possible behaviors of a concurrent system as a set of sequences of events. The constrained expression formalism provides a useful closed-form description of these sequences. Algorithms were developed for translating designs expressed in a wide variety of notations into these constrained expression descriptions. A number of powerful analysis techniques that can be applied to these descriptions have also been developed.