Improving the Accessibility of Lightweight Formal Verification Systems

In research areas involving mathematical rigor, there are numerous benefits to adopting a formal representation of models and arguments: reusability, automatic evaluation of examples, and verification of consistency and correctness. However, broad accessibility has not been a priority in the design of formal verification tools that can provide these benefits. We propose a few design criteria to address these issues: a simple, familiar, and conventional concrete syntax that is independent of any environment, application, or verification strategy, and the possibility of reducing workload and entry costs by employing features selectively. We demonstrate the feasibility of satisfying such criteria by presenting our own formal representation and verification system. Our system’s concrete syntax overlaps with English, LATEX and MediaWiki markup wherever possible, and its verifier relies on heuristic search techniques that make the formal authoring process more manageable and consistent with prevailing practices. We employ techniques and algorithms that ensure a simple, uniform, and flexible definition and design for the system, so that it easy to augment, extend, and improve.

Verification with Natural Contexts: Soundness of Safe Compositional Network Sketches

In research areas involving mathematical rigor, there are numerous benefits to adopting a formal representation of models and arguments: reusability, automatic evaluation of examples, and verification of consistency and correctness. However, accessibility has not been a priority in the design of formal verification tools that can provide these benefits. In earlier work [30] we attempt to address this broad problem by proposing several specific design criteria organized around the notion of a natural context: the sphere of awareness a working human user maintains of the relevant constructs, arguments, experiences, and background materials necessary to accomplish the task at hand. In this report we evaluate our proposed design criteria by utilizing within the context of novel research a formal reasoning system that is designed according to these criteria. In particular, we consider how the design and capabilities of the formal reasoning system that we employ influence, aid, or hinder our ability to accomplish a formal reasoning task – the assembly of a machine-verifiable proof pertaining to the NetSketch formalism. NetSketch is a tool for the specification of constrained-flow applications and the certification of desirable safety properties imposed thereon. NetSketch is conceived to assist system integrators in two types of activities: modeling and design. It provides capabilities for compositional analysis based on a strongly-typed domain-specific language (DSL) for describing and reasoning about constrained-flow networks and invariants that need to be enforced thereupon. In a companion paper [13] we overview NetSketch, highlight its salient features, and illustrate how it could be used in actual applications. In this paper, we define using a machine-readable syntax major parts of the formal system underlying the operation of NetSketch, along with its semantics and a corresponding notion of validity. We then provide a proof of soundness for the formalism that can be partially verified using a lightweight formal reasoning system that simulates natural contexts. A traditional presentation of these definitions and arguments can be found in the full report on the NetSketch formalism [12].

Lightweight Formal Verification in Classroom Instruction of Reasoning about Functional Code

In college courses dealing with material that requires mathematical rigor, the adoption of a machine-readable representation for formal arguments can be advantageous. Students can focus on a specific collection of constructs that are represented consistently. Examples and counterexamples can be evaluated. Assignments can be assembled and checked with the help of an automated formal reasoning system. However, usability and accessibility do not have a high priority and are not addressed sufficiently well in the design of many existing machine-readable representations and corresponding formal reasoning systems. In earlier work [Lap09], we attempt to address this broad problem by proposing several specific design criteria organized around the notion of a natural context: the sphere of awareness a working human user maintains of the relevant constructs, arguments, experiences, and background materials necessary to accomplish the task at hand. We report on our attempt to evaluate our proposed design criteria by deploying within the classroom a lightweight formal verification system designed according to these criteria. The lightweight formal verification system was used within the instruction of a common application of formal reasoning: proving by induction formal propositions about functional code. We present all of the formal reasoning examples and assignments considered during this deployment, most of which are drawn directly from an introductory text on functional programming. We demonstrate how the design of the system improves the effectiveness and understandability of the examples, and how it aids in the instruction of basic formal reasoning techniques. We make brief remarks about the practical and administrative implications of the system’s design from the perspectives of the student, the instructor, and the grader.

Self-organized vegetation patterning as a fingerprint of climate and human impact on semi-arid ecosystems

Spatially periodic vegetation patterns are well known in arid and semi-arid regions around the world. Mathematical models have been developed that attribute this phenomenon to a symmetry-breaking instability. Such models are based on the interplay between competitive and facilitative influences that the vegetation exerts on its own dynamics when it is constrained by arid conditions, but evidence for these predictions is still lacking. Moreover, not all models can account for the development of regularly spaced spots of bare ground in the absence of a soil prepattern. We applied Fourier analysis to high-resolution, remotely sensed data taken at either end of a 40-year interval in southern Niger. Statistical comparisons based on this textural characterization gave us broad-scale evidence that the decrease in rainfall over recent decades in the sub-Saharan Sahel has been accompanied by a detectable shift from homogeneous vegetation cover to spotted patterns marked by a spatial frequency of about 20 cycles km-1. Wood cutting and grazing by domestic animals have led to a much more marked transition in unprotected areas than in a protected reserve. Field measurements demonstrated that the dominant spatial frequency was endogenous rather than reflecting the spatial variation of any pre-existing heterogeneity in soil properties. All these results support the use of models that can account for periodic vegetation patterns without invoking substrate heterogeneity or anisotropy, and provide new elements for further developments, refinements and tests. This study underlines the potential of studying vegetation pattern properties for monitoring climatic and human impacts on the extensive fragile areas bordering hot deserts. Explicit consideration of vegetation self-patterning may also improve our understanding of vegetation and climate interactions in arid areas. © 2006 The Authors.

Nonlinear oscillator metamaterial model: numerical and experimental verification.

We verify numerically and experimentally the accuracy of an analytical model used to derive the effective nonlinear susceptibilities of a varactor-loaded split ring resonator (VLSRR) magnetic medium. For the numerical validation, a nonlinear oscillator model for the effective magnetization of the metamaterial is applied in conjunction with Maxwell equations and the two sets of equations solved numerically in the time-domain. The computed second harmonic generation (SHG) from a slab of a nonlinear material is then compared with the analytical model. The computed SHG is in excellent agreement with that predicted by the analytical model, both in terms of magnitude and spectral characteristics. Moreover, experimental measurements of the power transmitted through a fabricated VLSRR metamaterial at several power levels are also in agreement with the model, illustrating that the effective medium techniques associated with metamaterials can accurately be transitioned to nonlinear systems.

Automatic verification of linear controller software

© 2015 IEEE.We consider the problem of verification of software implementations of linear time-invariant controllers. Commonly, different implementations use different representations of the controller's state, for example due to optimizations in a third-party code generator. To accommodate this variation, we exploit input-output controller specification captured by the controller's transfer function and show how to automatically verify correctness of C code controller implementations using a Frama-C/Why3/Z3 toolchain. Scalability of the approach is evaluated using randomly generated controller specifications of realistic size.

A verification system for cinematographer image generation tools

The Production Workstation developed at the University of Greenwich is evaluated as a tool for assisting all those concerned with production. It enables the producer, director, and cinematographer to explore the quality of the images obtainable when using a plethora of tools. Users are free to explore many possible choices, ranging from 35mm to DV, and combine them with the many image manipulation tools of the cinematographer. The validation required for the system is explicitly examined, concerning the accuracy of the resulting imagery. Copyright © 1999 by the Society of Motion Picture and Television Engineers, Inc.

Manufacturing knowledge verification in design support systems

This paper identifies the need for a verification methodology for manufacturing knowledge in design support systems; and proposes a suitable methodology based on the concept of ontological commitment and the PSL ontology (ISO/CD18629). The use of the verification procedures within an overall system development methodology is examined, and an understanding of how various categories of manufacturing knowledge (typical to design support systems) map onto the PSL ontology is developed. This work is also supported by case study material from industrial situations, including the casting and machining of metallic components. The PSL ontology was found to support the verification of most categories of manufacturing knowledge, and was shown to be particularly suited to process planning representations. Additional concepts and verification procedures were however needed to verify relationships between products and manufacturing processes. Suitable representational concepts and verification procedures were therefore developed, and integrated into the proposed knowledge verification methodology.

Prediction and Verification of miRNA Expression in Human and Rat Retinas.

PURPOSE: MicroRNAs (miRNAs) play a global role in regulating gene expression and have important tissue-specific functions. Little is known about their role in the retina. The purpose of this study was to establish the retinal expression of those miRNAs predicted to target genes involved in vision. METHODS: miRNAs potentially targeting important "retinal" genes, as defined by expression pattern and implication in disease, were predicted using a published algorithm (TargetScan; Envisioneering Medical Technologies, St. Louis, MO). The presence of candidate miRNAs in human and rat retinal RNA was assessed by RT-PCR. cDNA levels for each miRNA were determined by quantitative PCR. The ability to discriminate between miRNAs varying by a single nucleotide was assessed. The activity of miR-124 and miR-29 against predicted target sites in Rdh10 and Impdh1 was tested by cotransfection of miRNA mimics and luciferase reporter plasmids. RESULTS: Sixty-seven miRNAs were predicted to target one or more of the 320 retinal genes listed herein. All 11 candidate miRNAs tested were expressed in the retina, including miR-7, miR-124, miR135a, and miR135b. Relative levels of individual miRNAs were similar between rats and humans. The Rdh10 3'UTR, which contains a predicted miR-124 target site, mediated the inhibition of luciferase activity by miR-124 mimics in cell culture. CONCLUSIONS: Many miRNAs likely to regulate genes important for retinal function are present in the retina. Conservation of miRNA retinal expression patterns from rats to humans supports evidence from other tissues that disruption of miRNAs is a likely cause of a range of visual abnormalities.

FPGA-based minutia matching for biometric fingerprint image database retrieval

In this paper, a parallel-matching processor architecture with early jump-out (EJO) control is proposed to carry out high-speed biometric fingerprint database retrieval. The processor performs the fingerprint retrieval by using minutia point matching. An EJO method is applied to the proposed architecture to speed up the large database retrieval. The processor is implemented on a Xilinx Virtex-E, and occupies 6,825 slices and runs at up to 65 MHz. The software/hardware co-simulation benchmark with a database of 10,000 fingerprints verifies that the matching speed can achieve the rate of up to 1.22 million fingerprints per second. EJO results in about a 22% gain in computing efficiency.

Cytotoxic alkaloids motuporamines A-C: Synthesis and structural verification

[GRAPHICS]