Title: Adventures in Foreign Function Interfaces

Speaker: Joel Stanley

        Galois, Inc.

Date: Tuesday, August 19th, 10.30am

Location: Galois, Inc.

        421 SW 6th Ave. Suite 300
        (3rd floor of the Commonwealth Building)
        Portland, Oregon

Abstract:

In-process integration and data exchange between multiple language
runtimes is a classic software engineering challenge.  This talk
describes our experiences in building an open-source tool for
generating an "FFI bridge" between Poly/ML and OCaml, via the common
C FFI provided by both language's runtimes.

The first intended use of this tool is to programmatically generate
a bridge between Isabelle (on the Poly/ML side) and Intel's Decision
Procedure Toolkit API (on the OCaml side).

About the Galois Tech Talks.

Galois (http://galois.com) has been holding weekly technical
seminars for several years on topics from functional programming,
formal methods, compiler and language design, to cryptography, and
operating system construction, with talks by many figures from the
programming language and formal methods communities.

The talks are open and free. If you're planning to attend, dropping
a note to <[email protected]> is appreciated, but not required.
If you're interested in giving a talk, we're always looking for new
speakers. 

Title: GpuGen: Bringing the Power of GPUs into the Haskell World

Speaker: Sean Lee

       Programming Languages & Systems
       UNSW, Sydney

Date: Tuesday, September 2nd.

       10.30am

Location: Galois, Inc.

       421 SW 6th Ave. Suite 300
       (3rd floor of the Commonwealth Building)
       Portland, Oregon

Abstract:

For the last decade, the performance of GPUs has out-grown CPUs, and their programmability has also improved to the level where they can be used fo general-purpose computations. Nonetheless, GPU programming is still limited only to those who understand the hardware architecture and the parallel processing. This is because the current GPU programming systems are based on the specialized parallel processing model, and require low-level attention in many aspects such as thread launching and synchronization.

The need for a programming system which provides a high-level abstraction layer on top of the GPU programming systems without losing the performance gain arises to facilitate the use of GPUs. Instead of writing a programming system from the scratch, the development of a Haskell extension has been chosen as the ideal approach, since the Haskell community has already accumulated a significant amount of research and resources for Nested Data Parallelism, which could be adopted to provide a high-level abstraction on GPU programming and even to broaden the applicability of GPU programming. In addition, the Foreign Function Interface of Haskell is sufficient to be the communication medium to the GPU.

GpuGen is what connects these two dots: GPUs and Haskell. It compiles the collective data operations such as scan, fold, map, etc, which incur most computation cost, to the GPU. The design of the system, the structure of the GpuGen compiler, and the current development status are to be discussed in the talk.

Biographical details:

Sean Lee is a PhD candidate at the UNSW, Sydney, working in the Programming Languages & Systems Group. This summer he's been interning at Nvidia in Santa Clara, working on programming GPUs with Haskell.

About the Galois Tech Talks.

Galois (http://galois.com) has been holding weekly technical seminars for several years on topics from functional programming, formal methods, compiler and language design, to cryptography, and operating system construction, with talks by many figures from the programming language and formal methods communities.

The talks are open and free. If you're planning to attend, dropping a note to [email protected] is appreciated, but not required. If you're interested in giving a talk, we're always looking for new speakers.

TITLE: Pretty-Printing a Really Long Formula (or, "What a Mathematician Could Learn from Haskell")

SPEAKER: Lee Pike, R&D Engineering, Galois, Inc.

DATE: Tuesday, September 9th. 10.30am

LOCATION:
Galois, Inc. 421 SW 6th Ave. Suite 300 (3rd floor of the Commonwealth Building) Portland, Oregon

ABSTRACT:

To the typical engineer or evaluator, mathematics can be scary, logic can be scarier, and really long specifications can simply be overwhelming. This talk is about the problem of the visual presentation of formal specifications clearly and concisely. We take as our initial inspiration Leslie Lamport's brief paper, "How to Write a Long Formula" and "How to Write a Proof" in which he proposes methods for writing the long and tedious formulas and proofs that appear in formal specification and verification.

I will describe the problem and present one particular solution, as implemented in a simple pretty-printer I've written (in Haskell), that uses indentation and labels to more easily visually parse long formulas. Ultimately, I propose a "HOL Normal Form" for presenting specifications, much like BNF is used for presenting language definitions.

BIOGRAPHICAL DETAILS:

http://galois.com/company/people/lee_pike/

ABOUT THE GALOIS TECH TALKS.

Galois (http://galois.com) has been holding weekly technical seminars for several years on topics from functional programming, formal methods, compiler and language design, to cryptography, and operating system construction, with talks by many figures from the programming language and formal methods communities.

The talks are open and free. If you're planning to attend, dropping a note to [email protected] is appreciated, but not required. If you're interested in giving a talk, we're always looking for new speakers.

Title: Left-fold enumerators

        Towards a safe, expressive and efficient I/O interface for Haskell

Speaker: Johan Tibell

        Software Engineer
        Google

Date: Monday, September 15th.

        1pm

Location: Galois, Inc.

        421 SW 6th Ave. Suite 300
        (3rd floor of the Commonwealth Building)
        Portland, Oregon

Abstract:

I will describe a programming style for I/O operations that is based on left-fold enumerators. This style of programming is more expressive than imperative style I/O represented by the Unix functions read and write, and safer than lazy I/O using streams. Left-fold enumerators offers both high-performance using block based I/O and safety in terms of error handling and resource usage. I will demonstrate Hyena, a web server prototype written in Haskell, as an example of left-fold enumerator style of programming.

This talk is intended as a starting point for further discussions on what would be a good interface for I/O rather than a presentation of finished research.

About the Galois Tech Talks.

Galois (http://galois.com) has been holding weekly technical seminars for several years on topics from functional programming, formal methods, compiler and language design, to cryptography, and operating system construction, with talks by many figures from the programming language and formal methods communities.

The talks are open and free. If you're planning to attend, dropping a note to  is appreciated, but not required. If you're interested in giving a talk, we're always looking for new speakers.

Title: Theorem Proving for Verification

Speaker: John Harrison

        Principal Engineer
        Intel

Date: Tuesday, September 16th.

        10.30am

Location: Galois, Inc.

        421 SW 6th Ave. Suite 300
        (3rd floor of the Commonwealth Building)
        Portland, Oregon

Abstract:

The theorem proving approach to verification involves modelling a system in a rich formalism such as higher-order logic or set theory, then performing a human-driven interactive correctness proof using a proof assistant. In a striking contrast, techniques like model checking, by limiting the user to a less expressive formalism (propositional logic, CTL etc.), can offer completely automated decision methods, making them substantially easier to use and often more productive.

With this in mind, why should one be interested in the theorem proving approach? In this tutorial I will explain some of the advantages of theorem proving, showing situations where the generality of theorem proving is beneficial, allowing us to tackle domains that are beyond the scope of automated methods or providing other important advantages. I will talk about the state of the art in theorem proving systems and and give a little demonstration to give an impression of what it's like to work with such a system.

Biographical details:

John Harrison has worked in formal verification and automated theorem proving since 1990, when he joined Mike Gordon's "Hardware Verification Group" (HVG) at the University of Cambridge Computer Laboratory. As well as working on the development of the HOL theorem prover, he developed a particular interest in the formalization of real analysis and its application to formal verification of floating-point hardware. His PhD in this area, "Theorem Proving with the Real Numbers", written under Mike Gordon's supervision, won a UK Distinguished Dissertation award and was published as a book. He also redesigned HOL from scratch, resulting in an alternative version called HOL Light. After completing his PhD research in 1995, John Harrison spent a very enjoyable year at Abo Akademi University and Turku Centre for Computer Science (TUCS) in Turku, Finland, where he was a member of Ralph Back's Programming Methods Research Group. Among other activities, he championed the "declarative" proofs of the Mizar system and showed how these could be integrated into other theorem-provers, work subsequently taken up in DECLARE, Isar and other systems.

John Harrison then returned to Cambridge and worked on a formal model of floating-point arithmetic and its application to the verification of some realistic algorithms for transcendental functions. This work attracted the attention of Intel, and in 1998 John Harrison joined the company as a Senior Software Engineer (now Principal Engineer) specializing in the design and formal verification of mathematical algorithms. He has formally verified and in many cases designed or redesigned numerous algorithms for mathematical functions including division, square root and transcendental functions.

In his limited spare time over the past 10 years, John Harrison has been working on a book giving a comprehensive introduction to automated theorem proving.  (http://www.cambridge.org/9780521899574)

About the Galois Tech Talks.

Galois (http://galois.com) has been holding weekly technical seminars for several years on topics from functional programming, formal methods, compiler and language design, to cryptography, and operating system construction, with talks by many figures from the programming language and formal methods communities.

The talks are open and free. If you're planning to attend, dropping a note to <[email protected]> is appreciated, but not required. If you're interested in giving a talk, we're always looking for new speakers.

Title: Bluespec: Advanced Modeling, Design and Verification using High-Level Synthesis Speaker: Rishiyur Nikhil CTO, Bluespec, Inc. Date: Thursday, October 2nd. 10.30am Location: Galois, Inc., 421 SW 6th Ave. Suite 300, (3rd floor of the Commonwealth Building)

ABSTRACT:

Over the past few years, several projects in major companies have been adopting BSV (Bluespec SystemVerilog) as their next-generation tool of choice for IP design, modeling (for both architecture exploration and early software development), and verification enviroments.

The reason for choosing BSV is its unique combination of:

(1) excellent computation model for expressing complex concurrency and communication, based on atomic transactions and atomic transactional inter-module methods

(2) very high level of abstraction and parameterization (principally inspired by Haskell)

(3) full synthesizability, enabling execution on FPGAs, obtaining better performance (3 to 4 orders of magnitude) and scalability than software simulation at comparable levels of detail.

In this presentation, I will provide a brief technical overview of BSV (points 1-3 above), and describe several customer projects using BSV. I will also briefly contrast BSV with other approaches to High Level Synthesis (particularly those based on C/C++/SystemC).

BIOGRAPHY:

Rishiyur S. Nikhil is co-founder and CTO of Bluespec, Inc., which develops tools that dramatically improve correctness, productivity, reuse and maintainability in the design, modeling and verification of digital designs (ASICs and FPGAs). The core technologies consist of a language, BSV (Bluespec SystemVerilog), which enables very abstract source descriptions based on scalable atomic transactions and extreme parameterization, and tools for high-quality synthesis of BSV into RTL. Earlier, from 2000 to 2003, he led a team inside Sandburst Corp. (later acquired by Broadcom) developing Bluespec technology and contributing to 10Gb/s enterprise network chip models, designs and design tools.

From 1991 to 2000 he was at Cambridge Research Laboratory (DEC/Compaq), including one and a half years as Acting Director. From 1984 to 1991 he was a professor of Computer Science and Engineering at MIT. He has led research teams, published widely, and holds several patents in functional programming, dataflow and multithreaded architectures, parallel processing, compiling, and EDA. He is a member of ACM and IFIP WG 2.8 on Functional Programming, and a Senior Member of IEEE. He received his Ph.D. and M.S.E.E. in Computer and Information Sciences from the Univ. of Pennsylvania, and his B.Tech in EE from IIT Kanpur.

ABOUT THE GALOIS TECH TALKS:

Galois (http://galois.com) has been holding weekly technical seminars for several years on topics from functional programming, formal methods, compiler and language design, to cryptography, and operating system construction, with talks by many figures from the programming language and formal methods communities.

The talks are open and free. If you're planning to attend, dropping a note to [email protected] is appreciated, but not required. If you're interested in giving a talk, we're always looking for new speakers.

Duncan Coutts, from Well-Typed (http://well-typed.com), will be giving a tech talk tomorrow about the technical direction of Cabal, Haskell package infrastructure, and the problems of managing very large amounts of Haskell code.

...

TITLE: The Future of Cabal -- "A language for build systems" and "Constraint solving problems in package deployment"

SPEAKER: Duncan Coutts, Well-Typed, LLP

DATE: Tuesday, Oct 7, 2008 10.30am

LOCATION: Galois, Inc. 421 SW 6th Ave. Suite 300 (3rd floor of the Commonwealth Building) Portland, Oregon

ABSTRACT:

This will be an informal talk and discussion on two topics:

1. A language for build systems

Build systems are easy to start but hard to get right. We'll take the view of a language designer and look at where our current tools fall down in terms of safety/correctness and expressiveness.

We'll then consider some very early ideas about what a build system language should look like and what properties it should have. Currently this takes the form of a design for a build DSL embedded in Haskell.

1. Constraint solving problems in package deployment

We are all familiar, at least peripherally, with package systems. Every Linux distribution has a notion of packages and most have high level tools to automate the installation of packages and all their dependencies. What is not immediately obvious is that the problem of resolving a consistent set of dependencies is hard, indeed it is NP-complete. It is possible to encode 3-SAT or Sudoku as a query on a specially crafted package repository.

We will look at this problem in a bit more detail and ask if the right approach might be to apply our knowledge about constraint solving rather than the current ad-hoc solvers that most real systems use. My hope is to provoke a discussion about the problem.

We can concentrate on one topic or the other depending on peoples interest.

ABOUT THE GALOIS TECH TALKS:

Galois (http://galois.com) has been holding weekly technical seminars for several years on topics from functional programming, formal methods, compiler and language design, to cryptography, and operating system construction, with talks by many figures from the programming language and formal methods communities.

The talks are open and free. If you're planning to attend, dropping a note to [email protected] is appreciated, but not required. If you're interested in giving a talk, we're always looking for new speakers.

Next week's tech talk, a special treat, with Jason Dagit (aka. lispy on

haskell) dropping by to talk about using GADTs to clean up darcs' patch

theory implementation.

TITLE: Type Correct Changes A Safe Approach to Version Control Implementation

speaker: Jason Dagit

LOCATION: Galois, Inc. 421 SW 6th Ave. Suite 300 (3rd floor of the Commonwealth Building) Portland, Oregon

ABSTRACT:

This will be a talk about Darcs and type safe manipulations of changes:

Darcs is based on a data model, known as Patch Theory, that sets it apart from other version control systems. The power of this data model is that it allows Darcs to manage significant complexity with a relatively straightforward user interface.

We show that Generalized Algebraic Data Types (GADTs) can be used to express several fundamental invariants and properties derived from Patch Theory. This gives our compiler, GHC, a way to statically enforce our adherence to the essential rules of our data model.

Finally, we examine how these techniques can improve the quality of the darcs codebase in practice.

PRESENTER:

Jason Dagit graduated from Oregon State University with B.S. degrees in Computer Science and Mathematics. He is currently employed at PTV America while completing his Masters degree at Oregon State under co-advisors Dr. David Roundy and Dr. Martin Erwig. During his time in graduate school he has studied both usability and programming languages. He participated in the 2007 Google Summer of Code where he worked under Dr. Roundy to improve Darcs conflict handling.

ABOUT THE GALOIS TECH TALKS:

Galois (http://galois.com) has been holding weekly technical seminars for several years on topics from functional programming, formal methods, compiler and language design, to cryptography, and operating system construction, with talks by many figures from the programming language and formal methods communities.

The talks are open and free. If you're planning to attend, dropping a note to [email protected] is appreciated, but not required. If you're interested in giving a talk, we're always looking for new speakers.

Factor is a programming language which has been in development for a little over 5 years. Factor is influenced by Forth, Lisp, Smalltalk. Factor takes the best ideas from Forth — simplicity, short, succint, code, emphasis on interactive testing, and meta-programming. Factor also brings modern high-level language features such as garbage collection, object orientation and functional programming familiar to users of languages such as Lisp, Smalltalk and Python. Finally, recognizing that no programming language is an island, Factor is portable, ships with a full-featured standard library, deploys stand-alone binaries, and interoperates with C and Objective-C.

In this talk, I will give the rationale for Factor’s creation, present an overview of the language, and show how Factor can be used to solve real-world problems with a minimum of fuss. At the same time, I will emphasize Factor’s extensible syntax, meta-programming and reflection capabilities, and show that these features, which are unheard of in the world of mainstream programming languages, make programs easier to write, more robust, and fun.

Biography:

Slava was born in the former USSR and emigrated to New Zealand at the age of 7. He moved to Ottawa, Canada when he was 18 to study for a Bachelors and Masters degree in Mathematics.  He now resides in Minneapolis, Minnesota. An early adopter of Java, Slava wrote the popular jEdit text editor, then went on to design and implement the Factor programming language. At his day job he hacks on web apps, optimizing compilers, garbage collectors, and everything in between

. Galois has been holding weekly technical seminars for several years on topics from functional programming, formal methods, compiler and language design, to cryptography, and operating system construction, with talks by many figures from the programming language and formal methods communities.

The talks are open and free. If you're planning to attend, dropping a note to is appreciated, but not required. If you're interested in giving a talk, we're always looking for new speakers.

PRESENTATION

Title: OpenTheory: Package Management for Higher Order Logic Theories

Speaker: Joe Hurd, Galois, Inc.

Abstract:

Interactive theorem has grown beyond toy examples in mathematics and program verification, as demonstrated by recent successes such as the Gonthier's formal proof of the four colour theorem and Leroy's verified compiler from a realistic subset of C into PowerPC assembly code. As the construction of large programs led to the development of software engineering techniques, there is now a need for theory engineering techniques to support these major verification efforts.

In this talk I will present the OpenTheory project, which has defined a simple 'article' format to represent theories of higher order logic. Theories in article format can be written by one higher order logic theorem prover, compressed by a standalone tool, stored and read by a different theorem prover. Articles naturally support theory interpretations, which leads to more efficient developments of standard theories, and also provides one approach to handling difficult constructs such as monads without extending the underlying logic. Finally, the grand vision of the OpenTheory article repository is painted, with fully automatic installation and dependency resolution.

ABOUT THE GALOIS TECH TALKS:

Galois (http://galois.com) has been holding weekly technical seminars for several years on topics from functional programming, formal methods, compiler and language design, to cryptography, and operating system construction, with talks by many figures from the programming language and formal methods communities.

The talks are open and free. If you're planning to attend, dropping a note to donsATgaloisDOTcom is appreciated, but not required. If you're interested in giving a talk, we're always looking for new speakers.

The next Galois Tech Talk, #2 for 2009, will be Isaac Potoczny-Jones (aka SyntaxNinja) on developing for the Android G1 phone.

The Android G1 is a TMobile phone whose operating system, Android is based on Linux and was developed by Google. It’s a very open smart-phone platform that rivals the iPhone.

While I’m no expert in Android or mobile platform development, I will discuss my experiences in Android development and demonstrate the toolchain used to develop software for the Android. I’ll outline the basic features of the platform, with a focus on the factors that make its openness so powerful:

* the inter-process communications mechanism whereby applications can advertise the services they offer and other applications can take advantage of those services,

* The open-source Java, Eclipse, and Linux-based toolchain,

* the OpenIntents project.

This will be an informal demonstration and discussion.

A group of us in collaboration between the Android Password Safe project and the Openintents project have implemented a cryptography service and a keystore service which other Android applications can use to keep data and passwords safe, in a way that’s convenient for the end user.

Our system allows a single password, and periodic single sign-on so that all applications can encrypt, decrypt, and store keys using the same master password that the user enters once. 

* Date: Tuesday, January 20, 2008
* Time: 10:30am - 11:30am
* Location: Galois, Inc.
  421 SW 6th Ave. Suite 300
  (3rd floor of the Commonwealth Building)
  Portland, OR 97204

Galois has been holding weekly technical seminars for several years on topics from functional programming, formal methods, compiler and language design, to cryptography, and operating system construction, with talks by many figures from the programming language and formal methods communities. The talks are open and free.

The next talk in the Galois Tech Seminar series:

[Note the Friday date, instead of the usual Tuesday slot!]

• Date: Friday, September 18th, 2009
• Title: Building Systems That Enforce Measurable Security Goals
• Speaker: Trent Jaeger
• Time: 10:30am - 11:30am
• Location: Galois, Inc. 421 SW 6th Ave. Suite 300; Portland, OR 97204

For details (including an abstract and speaker bio), please see our blog post: http://www.galois.com/blog/2009/09/10/jaegermeasurablesecurit/

An RSVP is not required; but feel free to drop a line to [email protected] if you've any questions or comments.

Levent Erkok

The next talk in the Galois Tech Seminar series:

• Date: Tuesday, October 6th, 2009
• Title: Roll Your Own Test Bed for Embedded Real-Time Protocols: A Haskell Experience
• Speaker: Lee Pike
• Time: 10:30am - 11:30am
• Location: Galois, Inc. 421 SW 6th Ave. Suite 300; Portland, OR 97204

For details (including an abstract and speaker bio), please see our blog post: http://www.galois.com/blog/2009/09/29/pike-haskell0/

Abstract: We present by example a new application domain for functional languages: emulators for embedded real-time protocols. As a case-study, we implement a simple emulator for the Biphase Mark Protocol, a physical-layer network protocol in Haskell. The surprising result is that a pure functional language with no built-in notion of time is extremely well-suited for constructing such emulators. Furthermore, we use Haskell’s property-checker QuickCheck to automatically generate real-time parameters for simulation. We also describe a novel use of QuickCheck as a probability calculator for reliability analysis.

Bio: Lee Pike is a member of the technical staff at Galois. Previously, he was a research scientist with the NASA Langley Formal Methods Group, primarily involved in the SPIDER project. His research interests include applying formal methods to safety-critical and security-critical applications, with a focus on industrial-scale endeavors.

An RSVP is not required; but feel free to drop a line to [email protected] if you've any questions or comments.

Levent Erkok

The next talk in the Galois Tech Seminar series:

• Date: Tuesday, October 13th, 2009
• Title: Constructing A Universal Domain for Reasoning About Haskell Datatypes
• Speaker: Brian Huffman
• Time: 10:30am - 11:30am
• Location: Galois, Inc. 421 SW 6th Ave. Suite 300; Portland, OR 97204

For details (including an abstract and speaker bio), please see our blog post: http://www.galois.com/blog/2009/10/06/huffman-universal/

An RSVP is not required; but feel free to drop a line to [email protected] if you've any questions or comments.

Levent Erkok

The next talk in the Galois Tech Seminar series:

• Date: Tuesday, October 20th, 2009
• Title: Writing Linux Kernel Modules with Haskell
• Speaker: Thomas DuBuisson
• Time: 10:30am - 11:30am
• Location: Galois, Inc. 421 SW 6th Ave. Suite 300; Portland, OR 97204

For details (including an abstract and speaker bio), please see our blog post: http://www.galois.com/blog/2009/10/13/haskellkernelmodules/

An RSVP is not required; but feel free to drop a line to [email protected] if you've any questions or comments.

Levent Erkok

The next talk in the Galois Tech Seminar series:

• Date: Tuesday, October 27th, 2009
• Title: How to choose between a screwdriver and a drill
• Speaker: Tanya L. Crenshaw
• Time: 10:30am - 11:30am
• Location: Galois, Inc. 421 SW 6th Ave. Suite 300; Portland, OR 97204

For details (including an abstract and speaker bio), please see our blog post: http://www.galois.com/blog/2009/10/20/crenshaw-simplex/

An RSVP is not required; but feel free to drop a line to [email protected] if you've any questions or comments.

Levent Erkok

The next talk in the Galois Tech Seminar series:

• Date: Tuesday, November 3rd, 2009
• Title: Testing First-Order-Logic Axioms in AutoCert
• Speaker: Ki Yung Ahn
• Time: 10:30am - 11:30am
• Location: Galois, Inc. 421 SW 6th Ave. Suite 300; Portland, OR 97204

For details (including an abstract and speaker bio), please see our blog post: http://www.galois.com/blog/2009/10/28/ahn-autocert/

An RSVP is not required; but feel free to drop a line to [email protected] if you've any questions or comments.

Levent Erkok

[NB. This talk is on Friday, instead of the usual Tuesday slot.]

The next talk in the Galois Tech Seminar series:

• Date: Friday, November 13th, 2009
• Title: Hoare-Logic – fiddly details and small print
• Speaker: Rod Chapman
• Time: 10:30am - 11:30am
• Location: Galois, Inc. 421 SW 6th Ave. Suite 300; Portland, OR 97204

For details (including an abstract and speaker bio), please see our blog post: http://www.galois.com/blog/2009/11/04/chapman-hoare/

An RSVP is not required; but feel free to drop a line to [email protected] if you've any questions or comments.

Levent Erkok

The December 15th Galois Tech Talk will be delivered by John Launchbury. He will present Conal Elliott’s 2009 ICFP paper entitled Beautiful Differentiation for those of us who were not able to attend this wonderful talk in-person.

Hello,

The next Galois Tech Talk will be "An Introduction to the Maude Formal Tool Environment", presented by Joe Hendrix on Tuesday, February 2nd, at 10:30am.

For more details, please visit: http://www.galois.com/blog/2010/01/29/tech-talk-an-introduction-to-the-maude-formal-tool-environment/

Hope to see you there! -Iavor

presenter: Mark Jones

abstract: Developers of systems software must often deal with low-level and performance-critical details that are hard to address in high-level programming languages. As a result, much of the systems software that is produced today is written in languages like C and assembly code, without the benefit of more expressive type systems or other features from modern functional programming languages that could help to increase programmer productivity or software quality. In this talk, we present an update on the status of Habit, a dialect of Haskell that we are designing, as part of the HASP project at PSU, to meet the needs of high assurance systems programming. Among other features, Habit provides: mechanisms for fine control over representation of bit-level and memory-based data structures; strong support for both functional and imperative programming; and a flexible type system that allows precise characterization of size and bound information via type level naturals, as well as termination properties resulting from the use of unpointed types.

The L4.verified Project Presented by Dr. Gerwin Klein.

Last year, the NICTA L4.verifed project produced a formal machine-checked Isabelle/HOL proof that the C code of the seL4 OS microkernel correctly implements its abstract implementation. This talk will give an overview of the proof together with its main implications and assumptions, and will show in which kinds of systems this formally verified kernel can be used for gaining assurance on overall system security.

presenter: Taras Glek

abstract: A competitive browser market requires fast-paced improvements to the codebase. Such improvements may require significant refactoring of large parts of the codebase. Mozilla Firefox is one of the largest open source C++ projects. Unfortunately C++ is a complex language: method overloading, virtual functions, template instantiation, pointer arithmetic, etc reduce developer productivity. Mozilla developed C++ static analysis and refactoring tools to increase developer leverage in C++. Static analysis is done via Dehydra/Treehydra GCC plugins and refactoring is accomplished by extending the Elsa C++ parser. This talk will discuss why Mozilla needs static analysis, why there are so few tools for C++, and specific projects that we’ve embarked on.

Introducing Well-Founded Recursion Eric Mertens

Implementing recursive functions can be tricky when you want to be certain that they eventually terminate. This talk introduces the concept of well-founded recursion as a tool for implementing recursive functions. It implements these concepts in the Agda programming language and demonstrates the technique by implementing a simple version of Quicksort.

Requirements and Performance of Data Intensive, Irregular Applications

Dr. John Feo

Many fundamental science, national security, and business applications need to process large volumes of irregular, unstructured data. Data collection and analysis is rapidly changing the way the scientific, national security, and economic communities operate. There are worldwide operational deployments of instruments to detect the proliferation of weapons of mass destruction, monitor terrorist cells, and track the movement of illicit goods and services. In the next 15 years 30% of battle-space defense forces will be autonomous with each advanced robotic device carrying dozens of sophisticated sensors collecting, processing, analyzing and transmitting large amounts of data. American economic competitiveness will depend increasingly on the timely analysis of many Petabytes of data collected in diverse computing clouds charting the social and economic behavior of consumers.

Unlike traditional scientific applications based on linear algebra routines, data analytic applications comprise large, integer-based graph computations with irregular data access patterns, low computation to memory access ratios, and high levels of fine grain parallelism that pass data and synchronize frequently. Traditional architectures optimized to run large-scale floating point intensive simulations are inadequate, and more suitable high-end architectures such as the Cray XMT are needed. In this talk I will discuss the programming language, tools, and system requirements for data analytic applications. I will survey the research at PNNL’s Center for Adaptive Supercomputer Software as regards graph analytics. In particular, I will present several key graph algorithms we have developed with an emphasis on structure, use of special hardware features, performance, and scalability.

Computers As We Don’t Know Them Christof Teuscher, PhD

Since the beginning of modern computer science some sixty years ago, we are building computers in pretty much the same way. Silicon transistor electronics serves as a physical device, the von Neumann architecture provides a computer design model, while the abstract Turing machine concept supports the theoretical foundations. However, in recent years, unimagined computing devices have seen the light because of advances in synthetic biology, nanotechnology, material science, and neuroscience. Many of these novel devices share the following characteristics: (1) they are made up from massive numbers of simple, stochastic components which (2) are embedded in 2D or 3D space in some disordered way. A grand challenge in consists in developing computing paradigms, design methodologies, formal frameworks, architectures, and tools that allow to reliably compute and efficiently solve problems with such devices. In this talk, I will outline my visionary and long-term research efforts to address the grand challenge of building, organizing, and programming future computing machines. First, I will review exemplary future and emerging computing devices and highlight the particular challenges that arise for performing computations them. I will then delineate potential solutions on how these challenges might be addressed. Self-assembled nano-scale cellular automata (CAs) and random boolean networks (RBNs) will serve as a simple showcase. I will also present the efforts underway to self-assemble massive-scale nanowire-based interconnect fabrics for spatial computers and what the challenges are in terms of computations and communication in such a non-classical system.

abcBridge: Functional interfaces for AIGs and SAT solving

Edward Z. Yang

SAT solvers are perhaps the most under-utilized high-tech tools that the modern software engineer has at their fingertips. An industrial strength SAT solver can solve most human generated NP-complete problems in time for lunch, and there are many, many practical problem domains which involve NP-complete problems. However, a major roadblock to using a SAT solver in your every day routine is translating your problem into SAT, and then running it on a highly optimized SAT solver, which is probably implemented in C or C++ and not your usual favorite programming language.

This talk is about the use, design and implementation of abcBridge, a set of Haskell bindings for ABC, a system for sequential synthesis and verification produced by the Berkeley Logic Synthesis and Verification Group. ABC looks at SAT solving from the following perspective: given two circuits of logic gates (ANDs and NOTs), are they equivalent? ABC is imperative C code: abcBridge provides a pure and type-safe interface for building and manipulating and-inverter graphs. We hope to release abcBridge soon as open source.

Presented by Priyank Kalla.

Applications in Cryptography require multiplication and exponentiation operations to be performed over Galois fields GF(2^k). Therefore, there has been quite an interest in the hardware design and optimization of such multipliers. This has led to impressive advancements in this area — such as the use of composite field decomposition techniques, use of Montgomery multiplication, among others.

My research group has recently begun investigations in the verification of such Galois Field multipliers. Unfortunately, the word-length (k) in such multipliers can be very large: typically, k = 256. Due to such large word-lengths, verification techniques based on decision diagrams, SAT and contemporary SMT solvers are infeasible. We are exploring the use of Computer Algebra techniques, mainly Groebner bases theory, to tackle this problem. In this talk, we will see why Groebner bases techniques look promising, while at the same time also studying the challanges that have to be overcome.

presenter: David Spivak

About five months ago I gave a talk here at Galois called “Databases are categories.” The basic idea was that a database schema can be represented as a category C and its states can be represented as functors C–>Set. In this talk I’ll refine that notion a bit, explaining that schemas are better represented as sketches. I’ll also show how, within this model one can: deal with incomplete data; incorporate typing and calculated fields; and perform queries, define views, and migrate data between disparate schemas. That is, I’ll try to show that the categorical approach handles everything one might hope it would. Finally, I’ll discuss a linguistic version of categories, called “ologs,” and show how they may help to democratize information storage.

Presented by Lee Pike.

We address the problem of runtime monitoring for hard real-time programs—a domain in which correctness is critical yet has largely been overlooked in the runtime monitoring community. We describe the challenges to runtime monitoring for this domain as well as an approach to satisfy the challenges. The core of our approach is a language and compiler called Copilot. Copilot is a stream-based dataflow language that generates small constant-time and constant-space C programs, implementing embedded monitors. Copilot also generates its own scheduler, obviating the need for an underlying real-time operating system. This talk will include fun pictures and videos.

speaker: Alwyn Goodloe

Critical cyber-physical systems, such as avionics, typically have one or more components that control the behavior of dynamical physical systems. The design of such control systems is well understood with mature and sophisticated foundations, but control engineers typically only work on Matlab/Simulink models, ignoring the implementation all together. I will speak about an ongoing collaboration with Prof. Eric Feron of Georgia Tech aimed at narrowing this gap. I will briefly describe the design of a Matlab to C translator being written in Haskell and verified using the Frama-C tool and the Prototype Verification System (PVS). In addition, I will give a survey of our efforts in enhancing PVS’ capabilities in this area by building a Linear Algebra library targeted at the math used by control engineers.

Presented by Brian Ford

Ruby is a highly dynamic, strongly-typed programming language created by Yukihiro Matsumoto in 1993 and first released in 1995. It borrows from Smalltalk, Lisp, and Perl. Ruby has single inheritance, mixins, and syntax features like omission of parentheses that make it well-suited for embedded domain-specific languages. Ruby was popularized by the Ruby on Rails web development framework.

The Rubinius project began as an implementation of the Ruby programming language roughly following the design of the Smalltalk-80 virtual machine described in the Blue book (“Smalltalk-80: the language and its implementation” by Adele Goldberg and David Robson). We have extended the initial implementation based on modern research in virtual machines, garbage collectors, and just-in-time (JIT) compilers. Rubinius currently features a stack-oriented opcode virtual machine, generational garbage collector, and LLVM-based JIT compiler. Most of the Ruby core library and the bytecode compiler are written in Ruby.

We will examine the main features of Rubinius and take a deeper dive into some aspects of the virtual machine and JIT compiler. We will also look at possible future work to address memory load, startup, and suitability for using Rubinius in Android phones. If there is time and interest, we will discuss implementing programming languages besides Ruby on Rubinius.

Presented by Brian Ford

Ruby is a highly dynamic, strongly-typed programming language created by Yukihiro Matsumoto in 1993 and first released in 1995. It borrows from Smalltalk, Lisp, and Perl. Ruby has single inheritance, mixins, and syntax features like omission of parentheses that make it well-suited for embedded domain-specific languages. Ruby was popularized by the Ruby on Rails web development framework.

The Rubinius project began as an implementation of the Ruby programming language roughly following the design of the Smalltalk-80 virtual machine described in the Blue book (“Smalltalk-80: the language and its implementation” by Adele Goldberg and David Robson). We have extended the initial implementation based on modern research in virtual machines, garbage collectors, and just-in-time (JIT) compilers. Rubinius currently features a stack-oriented opcode virtual machine, generational garbage collector, and LLVM-based JIT compiler. Most of the Ruby core library and the bytecode compiler are written in Ruby.

We will examine the main features of Rubinius and take a deeper dive into some aspects of the virtual machine and JIT compiler. We will also look at possible future work to address memory load, startup, and suitability for using Rubinius in Android phones. If there is time and interest, we will discuss implementing programming languages besides Ruby on Rubinius.

Presented by Rebekah Leslie.

The existing implementation of DDT uses a depth-first search algorithm to drive the exploration of new paths for testing. This algorithm provides full coverage of the program under test, but is limited by the fact that the number of paths increases exponentially with the size of the program. By employing the control-flow graph information of the program under test, we can direct the testing process towards program paths that contain unvisited points and therefore obtain full branch coverage in a smaller number of tests than would be required by the original depth-first search algorithm. We will present two uses of control-flow graph information in DDT. The first use is a refinement of depth-first search where control-flow graph information is used to prune the search space to eliminate unnecessary tests. The second use is in the context of a prioritized work-queue that forms the basis for a variety of sophisticated search algorithms that exploit different heuristics.

Presented by Aaron Tomb.

Many tools exist to automate the search for defects in software source code. However, many of these tools have not been widely applied, partly because they tend to work least well in the most common case: on large software systems that have only partial specifications describing correct behavior --- often a collection of independent assertions sprinkled throughout the program.

Recent research has suggested that a large class of software bugs fall into the category of inconsistencies, or cases where two pieces of program code make incompatible assumptions. Existing approaches to inconsistency detection have used intentionally unsound techniques aimed at bug-finding rather than verification. In this dissertation, we describe an inconsistency detection analysis that subsumes previous work and is instead based on the foundation of the weakest precondition calculus.

We have applied our analysis to a large body of widely-used open-source software, and found a number of bugs.

Presented by Simon Winwood.

In 2009 the NICTA L4.verified project completed the machine-checked correctness proof of the seL4 microkernel. The natural next step is then to use this verified kernel to construct verified systems.

In this talk I give an overview of the ongoing work into systems verification in the Trustworthy Embedded Systems project. In particular, I will focus on the use of access control results to reason about the properties of systems in the presence of large untrusted components, such as a Linux kernel.

Presented by Grant Passmore.

In automated deduction, strategy is a vital ingredient in effective proof search. Strategy comes in many forms, but the key is this: user-specifiable adaptations of general reasoning mechanisms reduce the search space by tailoring its exploration to a particular class of problems. In fully automatic theorem provers, this may happen through formula weights, term orders and quantifier triggers. In interactive proof assistants, one may build strategies by programming tactics and carefully crafting systems of rewrite rules. Given that automated deduction often takes place over undecidable theories, the recognition of a need for strategy is natural and happened early in the field. In computer algebra, the situation is rather different.

In computer algebra, the theories one works over are often decidable but inherently infeasible. For instance, the theory of real closed fields (i.e., nonlinear real arithmetic) is decidable, but any full quantifier elimination algorithm for it is guaranteed to have worst-case doubly exponential time complexity. The situation is similar with algebraically closed fields (e.g., through Groebner bases), and many others. Usually, decision procedures arising from computer algebra admit little means for a user to control them. But, when it comes to practical applications, is an infeasible theory really so different from an undecidable one?

The Strategy Challenge in Computer Algebra is this: To build theoretical and practical tools allowing users to exert strategic control over the execution of core computer algebra algorithms. In this way, such algorithms may be tailored to specific problem domains. For formal verification efforts, the focus of this challenge upon decision procedures is especially relevant. In this talk, we will motivate this challenge and present two examples from our dissertation: (i) the theory of Abstract Groebner Bases and its use in developing new Groebner basis algorithms tailored to the needs of SMT solvers (joint with Leo de Moura), and (ii) the theory of Abstract Cylindrical Algebraic Decomposition and a family of real quantifier elimination algorithms tailored to the structure of nonlinear real arithmetic problems arising in specific formal verification tool-chains. The former forms the foundation of nonlinear arithmetic in the SMT solver Z3, and the latter forms the basis of our tool RAHD (Real Algebra in High Dimensions).

Presented by Johan Tibell.

The most commonly used map (dictionary) data type in Haskell is implemented using a size balanced tree. While size balanced trees provide good asymptotic performance, their real world performance is not stellar, especially when used with keys which are expensive to compare, such as strings.

In this talk we will look at two different map implementations that use hashing to achieve better real world performance. The implementations have different performance characteristics: one provides very fast look-ups while the other trades better insert performance for somewhat slower look-ups. I will describe the design of these data structures and show some early benchmark results.

Presented by Rachel Lanigan.

Engineers Without Borders USA is a fast-growing national non-profit impacting developing communities around the world. EWB provides an opportunity for engineering students and professionals to use their skills to develop sustainable, appropriate technologies for specific applications, to help meet the basic needs of people. Our programs typically start with a focus on providing water and sanitation, but often move into other areas depending on the needs of the people. There is a role for everyone at EWB, from engineers to public health professionals. Rachel will give a background on EWB, our local chapter, and how to get involved.

Presented by Philip Weaver.

Janrain offers user management services that include single sign-on, social login, and profile storage. We have recently begun using Haskell extensively to implement our products, and would like to share what the experience has been like.

In this talk we will give a technical demonstration of Capture, whose backend is written in Haskell, discuss some of the implementation details of Capture, and look at some of the joys and pitfalls that we experienced.

Presented by Joe Hurd.

Interactive theorem proving is tackling ever larger formalization and verification projects, and there is a critical need for theory engineering techniques to support these efforts. One such technique is cross-prover package management, which has the potential to simplify the development of logical theories and effectively share theories between different theorem prover implementations. The OpenTheory project has developed standards for packaging theories of the higher order logic implemented by the HOL family of theorem provers. What is currently missing is a standard theory library that can serve as a published contract of interoperability and contain proofs of basic properties that would otherwise appear in many theory packages. This talk will present a standard theory library for higher order logic represented as an OpenTheory package. We identify the core theory set of the HOL family of theorem provers, and describe the process of instrumenting the HOL Light theorem prover to extract a standardized version of its core theory development. We profile the axioms and theorems of our standard theory library and investigate the performance cost of separating the standard theory library into coherent hierarchical theory packages.

Presented by Jim Snow.

RNA Networks is a software company focused on providing the next generation storage cache solution that addresses performance deficiencies and the rising cost of storage for virtual environments. Our software solution utilizes compute resources (DRAM and flash) as a distributed clustered cache moving 'active' data off of the storage tier and into the compute tier translating to significant performance gains with no additional investment in hardware resources. RNA's MVX technology is based on a distributed shared memory core that leverages RDMA fabrics and allows for a unified and flexible namespace that can scale proportionally to meet any performance or capacity need.

In this presentation we'll discuss the core architecture and how this can be leveraged to both reduce the cost of high end storage and meet high performance storage objectives.

Presented by Chad Scherrer.

Sampling from a large discrete distribution is a common problem in statistics. In this talk, we'll consider a real-world situation where the properties of the distribution cause common approaches to break down, and we'll arrive at a Haskell-based solution that fixes the problem.

Presented by Nicholas Begley, Dave Dung Anh, James Heilinger, Alec Rasmussen, and Mark Theuson.

It's a bird! It's a plane! No, it's an open-source autonomous quad-copter. In collaboration with the Portland State University Electrical and Computer Engineering Dept., Galois mentored a Spring semester Senior Capstone Project to build an ArduCopter. The ArduCopter is based on the Arduino open-source hardware platform, and includes infrared sensors (collision avoidance), sonar and barometer (altitude hold), GPS (location), magnetometer (direction), and gyro (stabilization). This talk will include a description of the ArduCopter and it's operation, including the trials and tribulations of building and testing one. Of course, the talk will include cool videos.

Presented by Temesghen Kahsai.

We give an overview of a parallel k-induction-based model checking architecture for verifying safety properties of synchronous systems. The architecture, which is strictly message-based, is designed to minimize synchronization delays and easily accommodate the incorporation of incremental invariant generators to enhance basic k-induction. A first level of parallelism is introduced in the k-induction procedure itself by executing the base and the inductive steps concurrently. A second level of parallelism allows the addition of one or more independent processes that incrementally generate invariants for the system being verified. The invariants are fed to the k-induction loop as soon as they are produced and used to strengthen the induction hypothesis.

This architecture allows the verification of multiple properties in an incremental fashion. Specifically, the outcome of a property -- valid or invalid -- is communicated to the user as soon as the result is known. Moreover, verified valid properties are added as invariants in the model checking procedure to aid the verification of the remaining properties.

We provide experimental evidence that this incremental and parallel architecture significantly speeds up the verification of safety properties. Additionally, due to the automatic invariant generation, it also considerably increases the number of provable safety properties.

Presented by Adam Foltzer.

Interpreters offer a convenient and intuitive way for programmers to reason about language behavior through denotational semantics. However in a setting like Coq, where all recursive functions must provably terminate, it is impossible to write interpreters for non-terminating languages. The standard alternative is to inductively define operational semantics, but this can yield proofs that are difficult to automate, particularly in the presence of changing language features.

This talk presents a combined approach, where an interpreter is used in combination with operational semantics to prove type preservation of a small functional language. To demonstrate the scalability of the Coq development, let expressions and a pair types will be added and preservation will be proved again with only one extra line of proof script.

This technique and development are adapted from Greg Morrisett's lectures at the 2011 Oregon Programming Languages Summer School, and are available at his web site.

Presented by Kristin Rozier

Formal behavioral specifications written early in the system-design process and communicated across all design phases have been shown to increase the efficiency, consistency, and quality of the system under development. To prevent introducing design or verification errors, it is crucial to test specifications for satisfiability. Our focus here is on specifications expressed in linear temporal logic (LTL).

We introduce a novel encoding of symbolic transition-based Buchi automata and a novel, ``sloppy,'' transition encoding, both of which result in improved scalability. We also define novel BDD variable orders based on tree decomposition of formula parse trees. We describe and extensively test a new multi-encoding approach utilizing these novel encoding techniques to create 30 encoding variations. We show that our novel encodings translate to significant, sometimes exponential, improvement over the current standard encoding for symbolic LTL satisfiability checking.

Details can be found here: http://ti.arc.nasa.gov/profile/kyrozier/.

Presented by Sebastian Niller and Nis N. Wegmann

1

title: Translation of Functionally Embedded Domain-specific Languages With Static Type Preservation by using Witnesses

abstract: Static type preservation automatically guarantees type-correctness of an embedded domain-specific language (eDSL) by tying its type system to that of the host-language. Not only does this obviate the need for a custom type checker, it also preserves type-correctness during code transformations and optimizations, and simplifies and increases the efficiency of interpreters. When implementing a translator from a source DSL with type preservation to a target DSL, the commonly chosen approach requires the incorporation of extensions in the source DSL specific to the target DSL, which, in cases where multiple back-ends are required, obfuscates the source DSL and decreases the overall modularity. We show that by using witnesses, a technique which facilitates the construction of type-level proofs, we can effectively cope with this issue and implement translators without extending the source DSL.

We have applied our approach on Copilot, a Haskell-embedded domain specific language for runtime monitoring of hard real-time distributed systems, and used it for implementing two back-ends targeting the Haskell-embedded languages Atom and SBV. Our approach restrains to the Haskell 2010 Standard except for existentially and universally quantified types.

2

title: From High-Level Languages to Monitoring Fault-Tolerant Hardware: Case-Studies of Runtime Verification Using Copilot

abstract: Failures of hard real-time systems can be caused by systematic faults in software and hardware, as well as by random hardware faults, and faults due to wear out of hardware components. Even if monitoring software is proven to comply to its specification, there is no guarantee that failing underlying hardware does not affect the monitors themselves. An application of distributed Copilot monitors to a redundant airspeed measurement system is presented. We show the use of monitors enables the system to withstand benign and Byzantine hardware and software faults.

The second part of the talk presents current work using Copilot to monitor the MAVLink protocol in flight of a sub-scale model of an Edge 540T aircraft.

Presented by Alexey Gotsman

Most major OS kernels today run on multiprocessor systems and are preemptive: it is possible for a process running in the kernel mode to get descheduled. Existing modular techniques for verifying concurrent code are not directly applicable in this setting: they rely on scheduling being implemented correctly, and in a preemptive kernel, the correctness of the scheduler is interdependent with the correctness of the code it schedules. This interdependency is even stronger in mainstream kernels, such as Linux, FreeBSD or XNU, where the scheduler and processes interact in complex ways. In this talk I will present the first logic that is able to decompose the verification of preemptive multiprocessor kernel code into verifying the scheduler and the rest of the kernel separately, even in the presence of complex interdependencies between the two components present in mainstream kernels. This is joint work with Hongseok Yang (University of Oxford, UK).

Presented by Kevin Butler

The complexity of modern operating systems makes securing them a challenging problem. However, changes in the computing model, such as the rise of cloud computing and smarter peripherals, have presented opportunities to reconsider system architectures, as we move from traditional "stove-pipe" computing to distributed systems. In particular, we can build trustworthy components that act to provide security in complex systems.

This talk discusses how new disk architectures may be exploited to aid the protection of systems by acting as policy decision and enforcement points. We prototype disks that enforce data immutability at the block level on critical system data, preventing malicious code from inserting itself into system configuration and boot files. We then examine how storage may be used to ensure the integrity state of hosts prior to allowing access to data, and how such a design improves the security of portable storage devices. Using continual measurements of system state, we show through formal reasoning that such a device enforces guarantees that data is read and written while the host is in a good state. Finally, we discuss some recent initiatives to assure the identity of the host and identify future directions for exploring the interface between storage and operating system security.

Presented by Dylan McNamee.

This talk is an introduction to the MILS (Multiple Independent Layers of Security) architecture, motivated by the challenge of enforcing various kinds of security policies. I'll describe the goals of policy enforcement, traditional means of implementing security enforcement mechanisms, and the emerging MILS architecture for enforcing policies with high assurance.

Presented by Eric Migicovsky.

Hardware is hard. At least that's what people always say. Building a hardware startup requires a broad base of technical knowledge, from electronics and manufacturing experience to aesthetic and interface design. But Eric Migicovsky chose to start a hardware company after graduating from engineering because he wanted to see something he designed become a physical reality.

inPulse is a $150 hackable Bluetooth smartwatch. It connects to your smartphone and displays notifications like incoming emails, calls, and calendar alerts right on your wrist. After launching an SDK, 3rd party developers have started to create apps for inPulse.

In his talk, Eric will share some honest stories and anecdotes from various stages of product development. He'll also talk about the costs, timeframes and failure modes of hardware startups.

Presented by Nate Foster.

The languages used to program networks today lack modern features. Programming them is a complicated task, and outages and infiltrations are frequent. We believe it is time to develop NETWORK PROGRAMMING LANGUAGES with the following essential features:

• High-level abstractions that give programmers direct control over the network, allowing them to specify what they want the network to do without worrying about how to implement it.

• Compositional constructs that facilitate modular reasoning about programs.

• Portability, allowing programs written for one platform to be used with different devices.

• Rigorous semantic foundations that precisely document the meaning of the language and provide a basis for building formal verification tools.

The Frenetic language addresses these challenges in the context of OpenFlow networks. It combines a streaming declarative query sub-language and a functional reactive sub-language that, together, provide many of the features listed above. Our implementation handles many low-level packet-processing details and keeps traffic in the "fast path" whenever possible.

Presented by David Lazar

Formal semantics is notoriously hard. The K semantic framework (http://k-framework.org/) is a system that makes the task of formally defining programming languages easy and practical. The primary goals of the K framework are modularity, expressivity, and executability. Adding a new language feature to a K definition does not require you to revisit and modify existing semantic rules. The K framework is able to concisely capture the semantics of non-determinism and concurrency. Each K definition automatically yields an interpreter for the language so that the definition can be tested for correctness. These features made it possible to develop a complete formal semantics of the C language in K. The first half of the talk will be an overview of the K semantic framework. We'll discuss the merits of the framework using the K definition of a complex toy language as a guiding example. The second half of the talk will focus on a work-in-progress formalization of Haskell 98 in K. We'll look at the challenges of formalizing Haskell and the applications of this work.

Presented by Borzoo Bonakdarpour.

Design and implementation of distributed systems often involve many subtleties due to their complex structure, non-determinism, and low atomicity as well as occurrence of unanticipated physical events such as faults. Thus, constructing correct distributed systems has always been a challenge and often subject to serious errors. We propose a method for generating distributed implementations from high-level component-based models that only employ simple synchronization primitives. The method is a sequence of three transformations preserving observational equivalence: (1) A transformation from a global state to a partial state model, (2) a transformation which replaces multi-party strong synchronization primitives in atomic components by point-to-point send/receive primitives based on asynchronous message passing, and (3) a final transformation to concrete distributed implementation based on platform and architecture. We study the properties of different transformations, in particular, performance criteria such as degree of parallelism and overhead for coordination.

The second part of the talk will focus on an automated technique for optimal instrumentation of multi-threaded programs for debugging and testing of concurrent data structures. We define a notion of observability that enables debuggers to trace back and locate errors through data-flow instrumentation. Observability in a concurrent program enables a debugger to extract the value of a set of desired variables through instrumenting another (possibly smaller) set of variables. We formulate an optimization problem that aims at minimizing the size of the latter set. Our experimental results on popular concurrent data structures (e.g., linked lists and red-black trees) show significant performance improvement in optimally-instrumented programs using our method as compared to ad-hoc over-instrumented programs.

Presented by Julien Schmaltz.

Communication fabrics constitute an important challenge for the design and verification of multicore architectures. To enable their formal analysis, micro-architectural models have been proposed as an efficient abstraction capturing the high-level structure of designs. Micro-architectural models also include a representation of the protocols using the communication fabrics. This combination of different aspects in a single model is crucial for deadlock verification. Deadlocks emerge or are prevented in this combination: a system with a deadlock-free communication network combined with a deadlock-free protocol may have deadlocks or a system with a network with deadlocks combined with a deadlock-free protocol may be deadlock-free. This combination also makes the verification problem more complicated. We will present an algorithm for efficient deadlock verification in micro-architectural models. We will discuss the limitations of this approach and point to future research direction. An important future application of our methodology is the verification of cache coherency at the level of micro-architectures.

Presented by Alan Mishchenko.

Last spring, in March 2010, Aaron Bradley published the first truly new bit-level symbolic model checking algorithm since Ken McMillan’s interpolation based model checking procedure introduced in 2003. Our experience with the algorithm suggests that it is stronger than interpolation on industrial problems, and that it is an important algorithm to study further. In this paper, we present a simplified and faster implementation of Bradley’s procedure, and discuss our successful and unsuccessful attempts to improve it.

Presented by Charles Parker

A basic problem in computer science is binary classification, in which an algorithm applies a binary label to data based on the presence or absence of some phenomenon. Problems of this type abound in areas as diverse as computational biology, multimedia indexing, and anomaly detection. Evaluating the performance of a binary labeling algorithm is itself a complex task, often based on a domain-dependent notion of the relative cost of "false positives" versus "false negatives". As these costs are often not available to researchers or engineers, a number of methods are used to provide a cost-independent analysis of performance. In this talk, I will examine a number of these methods both theoretically and experimentally. The presented results suggest a set of best practices for evaluating binary classification algorithms, while questioning whether a cost-independent analysis is even possible.

Presented by Chris Andrew, Kayla Seliner, Mark Craig, and Trang Nguyen.

On October 7, 2008, the flight control system of Qantas flight 72 malfunctioned without warning. The failure caused the aircraft to violently pitch down with an acceleration of -0.8g, pitching passengers and crew into the roof of the cabin resulting in many injuries. In the investigation that followed, the malfunction was attributed to a software problem in the Air Data Inertial Reference Unit. These units are utilized on all modern passenger jets, but are proprietary devices not open to public scrutiny.

This capstone project develops an open source Air Data Inertial Reference Unit using four redundant Arduino boards each with a microcontroller, 3D gyroscope and accelerometer. Faults are injected into the system through software and outputs are monitored over serial ports allowing the user to test effectiveness of fault-tolerant algorithms to mask fail silent and byzantine faults in the sensors. Failures in ADIRU systems are usually complex in nature and arise under very anomalous circumstances suggesting that fault-tolerant system design could benefit from the diverse testing and evaluation that can occur in an open source community. This project demonstrates the low entry-cost to building a fault-tolerant system for open-source design and experimentation.

Presented by Sergio Antoy from Portland State University.

In this talk, I will introduce narrowing, the characterizing feature of functional logic programming, from the programmer's viepoint. Narrowing promotes non-determinism and it enables computing with incomplete or unknown information. After a short and informal presentation of Curry, the leading functional logic language, I will discuss a few examples showing that narrowing and its associated non-determinism support programming at a very high level of abstraction.

Presented by Iulian Neamtiu.

The relative novelty and rapid evolution pace of the Android ecosystem (platform, vendor-installed apps and third-party apps) means both the platform and apps receive little scrutiny. Hence there is a need for tools that assess, monitor and verify all components of the Android ecosystem. This lack of tools and scrutiny is particularly problematic when combined with the open nature of Google Play, the main app distribution channel.

In the first part of this talk we will focus on multi-layer profiling of Android apps using ProfileDroid, a tool and framework we developed at UC Riverside. ProfileDroid is useful for a variety of Android app analyses, from performance to usability to security. ProfileDroid monitors and correlates the behavior of an app at four layers: (a) static, or app specification (b) user interaction, (c) operating system, and (d) network layer. Using ProfileDroid on 27 free and paid Android apps, we have revealed: (a) discrepancies between the app specification and app execution, (b) free versions of apps could end up costing more than their paid counterparts, due to an order of magnitude increase in traffic, (c) most network traffic is not encrypted, (d) apps communicate with many more sources than users might expect.

In the second part of the talk we will present results from our long-term permission evolution study of the Android ecosystem---platform and 237 apps---over three years. We found that the platform has increased the number of dangerous permissions and does not move towards finer-grained permissions, and that app developers do not follow the principle of least privilege. We will also briefly discuss our efforts with static information flow tracking for Android apps, as well as building a log-and-replay system for Android.

Presented by Larry Diehl.

Many advanced branches of mathematics involve structures that abstract over well known specific instances, e.g. abstract algebraic structures, equivalence relations, various orders, category theoretic structures, etc. In typed functional programming (e.g. with type classes in Haskell), encoding such structures amounts to enforcing the definition of elements and operations for a particular structure instance on one hand, and being able to use said elements and operations in generic definitions on the other hand. With Dependently Typed Programming (DTP) we can go one step further and define propositions/properties for abstract structures, and subsequently require proofs in particular instances.

This talk will tell the story of how examples of particular instances inspire an abstract definition (including its propositional properties), how to then instantiate the original concrete examples in the new abstract definition, and finally create further abstract definitions that depend on previously defined ones. Emphasis will be given on how easily concrete proofs can be used as evidence for abstract propositions, and how proofs about abstract structures parameterized by other abstract structures may reuse their proofs (similar to the more common concept of reusing operations in subsequent abstract definitions). The talk will use Agda as its demonstration language, but proofs will mostly be in the form of equational reasoning that should look familiar to the non-expert.

Presented by Brian Huffman.

We present techniques for reasoning about constructor classes that (like the monad class) fix polymorphic operations and assert polymorphic axioms. We do not require a logic with first-class type constructors, first-class polymorphism, or type quantification; instead, we rely on a domain-theoretic model of the type system in a universal domain to provide these features. These ideas are implemented in the Tycon library for the Isabelle theorem prover, which builds on the HOLCF library of domain theory. The Tycon library provides various axiomatic type constructor classes, including functors and monads. It also provides automation for instantiating those classes, and for defining further subclasses. We use the Tycon library to formalize three Haskell monad transformers: the error transformer, the writer transformer, and the resumption transformer. The error and writer transformers do not universally preserve the monad laws; however, we establish datatype invariants for each, showing that they are valid monads when viewed as abstract datatypes.

Presented by Matthew Fernandez.

In safety- and security-critical environments software failures that are acceptable in other contexts may have expensive or even life-threatening consequences. Formal verification has the potential to provide high assurance for this software, but is regarded as being prohibitively expensive. Although significant advances have been made in this area, verification of larger systems still remains impractical. Component-based development has the potential to lower the cost of system-wide verification, bringing correctness proofs of these large scale systems within reach. This talk will discuss my work that aims to provide a component-based development environment for building systems with high assurance requirements. By providing a formal model of the platform with proven correctness properties that hold at the level of an abstract model right down to the implementation, I hope to reduce the cost of full system verification by allowing reasoning about system components in isolation.

Presented by Daniel Matichuk.

Formal verification can provide a high degree of assurance for critical software, but can come at the cost of large artefacts that must be maintained alongside it. When using an interactive theorem prover, these artefacts take the form of large, complex proofs where the ability to reuse and maintain them becomes paramount. I will present my work on a function annotation logic, which is an extension to Hoare logic that allows reasoning on intermediate program states to be easily reused. Program functions are annotated with properties as a side-condition of existing proofs. These annotations can reduce the proof burden substantially when subsequent program properties need to be shown. Implemented in Isabelle, it is shown to be practically useful by greatly simplifying cases where existing proofs contained largely duplicated reasoning.

Presented by Brian Huffman.

A polymorphic function may be instantiated at many different types; if the function is parametrically polymorphic, then all of its instances must behave uniformly. Reynolds' parametricity theorem expresses this precisely, in terms of binary relations derived from types. One application of the parametricity theorem is to derive Wadler-style "free theorems" about a polymorphic function from its type; e.g. rev :: [a] -> [a] must satisfy map f (rev xs) = rev (map f xs).

In this talk, I will show how to apply many of the ideas behind parametricity and free theorems in a new setting: formal reasoning about quotient types. Using types-as-binary-relations, we can automatically prove that corresponding propositions about quotient types and their representation types are logically equivalent. This design is implemented as the Transfer package in the Isabelle theorem prover, where it is used to automate many proofs about quotient types.

Presented by Erlend Hamberg.

An important problem in genetics is phylogenetic inference: Coming up with good hypotheses for the evolutionary relationship between species – usually represented as a “family tree”. As the amount of molecular data (e.g. DNA sequences) quickly grows, efficient algorithms become increasingly important to analyze this data. A maximum-likelihood approach with models for nucleotide evolution allows us to use all the sequence data, but is a computationally expensive approach. The number of possible trees also grows rapidly as we include more species. It is therefore necessary to use heuristic search methods to find good hypotheses for the “true” tree. Evolutionary algorithms (EA) is a class of such search/optimization algorithms that has been shown to perform well in other areas where the search space is large and irregular. I will explain my approach and my findings from using an evolutionary algorithm for inferring phylogenies from molecular data.

Presented by Andrew Farmer.

The importance of reasoning about and refactoring programs is a central tenet of functional programming. Yet our compilers and development toolchains only provide rudimentary support for these tasks, leaving the programmer to do them by hand. This talk introduces HERMIT, a toolkit enabling informal but systematic transformation of Haskell programs from inside the Glasgow Haskell Compiler's optimization pipeline. With HERMIT, users can experiment with optimizations and equational reasoning, while the tedious heavy lifting of performing the actual transformations is done for them. The talk will explore design choices in HERMIT, demonstrate its use on examples, and seek input for further development and case studies.

Presented by Joe FitzPatrick.

Generally, there is a very low barrier to entry when it comes to software or network-based attacks due to the fact that actual costs are minimal and most resources are readily available. This does mean that it's generally much easier to attack the software of a system than the hardware, but unfortunately that also leads to overconfidence in, as well as misplaced trust in hardware.

There is a clear 'hierarchy of attacks' in the hardware world. There are costs, often significant, involved in acquiring your hardware 'target' which might be damaged or destroyed in the process. There are a number of useful tools that cost anywhere from a few dollars to a few million dollars. I'll give a couple examples of what's possible within budgets of $100, $10,000, and $1,000,000. I'll point out how many capabilities are much more accessible than most assume, and how vulnerable to sub-$100 attacks most of our 'secure' hardware really is.

Five students in PSU’s Electrical and Computer Engineering Senior Capstone sequence want to show you what they’ve created: an inexpensive computer vision system for a quadcopter running on a Raspberry Pi board. One might be surprised how simple it is to code a decent object tracking algorithm using open-source software, and how difficult it is to keep a quadcopter from crashing into the wall in the debug stage. This talk should appeal to the RC hobbyist, the embedded systems programmer, and anyone interested in the art of computer vision. The presentation will include video footage of what these students have accomplished and how they pulled it off.

Presented by Gerwin Klein and Thomas Sewell.

This talk introduces two new facets that have recently been added to the seL4 formal verification story: a proof the kernel does not leak information between domains, and a proof that the compiled binary matches the expected semantics of the C source code.

The first part of the talk presents a new non-interference theorem for seL4, which builds on the earlier function correctness verification. The theorem shows how seL4 can be configured as a static separation kernel with dynamic kernel services within each domain.

The binary proof addresses the compiler-correctness assumption of the earlier seL4 proofs by connecting the compiled binary to the refinement chain, thus showing that the seL4 binary used in practice has all of the properties that have been shown of its models. We use the Cambridge ARM model and Magnus Myreen's certifying decompiler, together with a custom correspondence finder for assembly-like programs powered by modern SMT solvers. We cover the previously-verified parts of seL4 as compiled by gcc (4.5.1) at optimisation level 1.

Presented by Neil Sculthorpe.

In Haskell, there are many data types that would form monads were it not for the presence of type-class constraints on the operations on that data type. This is a frustrating problem in practice, because there is a considerable amount of support and infrastructure for monads that these data types cannot use. This talk will demonstrate that a monadic computation can be restructured into a normal form such that the standard monad class can be used. The technique is not specific to monads --- it can also be applied to other structures, such as applicative functors. One significant use case for this technique is Domain Specific Languages, where it is often desirable to compile a deep embedding of a computation to some other language, which requires restricting the types that can appear in that computation.

Presented by Pat Hickey.

At Galois, we're building critical flight control software using new software methods for embedded systems programming. We will show how we used new domain-specific languages which permit low-level hardware manipulation while still providing guarantees of type and memory safety. The flagship application for these new languages is called SMACCMPilot, a clean slate design of quadcopter flight control software built on open-source hardware. This talk will introduce our new software methods and show how we built SMACCMPilot to be high assurance without sacrificing programmer productivity.

Presented by Jesse Hallett.

Take control of your hardware by installing an open build of Android. Get root access and extend the life of your device. Learn about what is involved in installing a third-party OS on your phone or tablet.

Academic papers often describe typed calculi, but it is rare to find one in a production compiler. Indeed, I think the Glasgow Haskell Compiler (GHC) may be the only production compiler in the world that really has a remorselessly statically-typed intermediate language, informally called "Core", or (when writing academic papers) the more respectable-sounding "System FC".

As real compilers go, GHC's Core language is tiny: it is a slight extension of System F, with letrec, data types, and case expressions. Yet all of Haskell (now a bit of a monster) gets translated into it. In the last few years we have added one new feature to Core, namely typed (but erasable) coercions that witness type equalities, which turn Core into a particular kind of proof-carrying code. This single addition has opened the door to a range of source-language extensions, such as GADTs and type families.

In this talk I'll describe Core, and how it has affected GHC's development over the last two decades, concentrating particularly on recent developments, coercions, evidence, and type families. To test your mettle I hope to end up with the problem we are currently wrestling with: proving consistency of a non-terminating rewrite system with non-left-linear rules.

Presented by Alex Groce.

One of the most effective ways to test complex language implementations, file systems, and other critical systems software is random test generation. This talk will cover a number of recent results that show how---despite the importance of hand-tooled random test generators for complex testing targets--- there are methods that can be easily applied in almost any setting to greatly improve the effectiveness of random testing. Surprisingly, giving up on potentially finding any bug with every test makes it possible to find more bugs over all. The practical problem of finding distinct bugs in a large set of randomly generated tests, where the frequency of some bugs may be orders of magnitude higher than other bugs, is also open to non ad-hoc methods.

Small unmanned aircraft---more often called drones---are set to make a big impact on agriculture. You already know about military drones operating overseas, and perhaps you've even seen recreational drones starring in youtube videos, but as the FAA begins permitting commercial use of unmanned aircraft in 2015, you'll see drones replacing all sorts of roles that used to require a manned aircraft, and taking on new roles made possible by their low cost, versatility, and safety.

Chris Anderson will speak about the upcoming role of drones in agriculture, a field Chris says "is a big data problem without the big data." Chris will describe how farmers can will drones to curb plant disease, conserve water, and reduce pesticide and fertilizer use. He'll discuss the challenges ahead to integrate air vehicle systems with sensors, specialized cameras, and data processing.

presented by: Ashe Dryden

abstract: It's been scientifically proven that more diverse communities and workplaces create better products and the solutions to difficult problems are more complete and diverse themselves. Companies are struggling to find adequate talent. So why do we see so few women, people of color, and LGBTQ people at our events and on the about pages of our websites? Even more curiously, why do 60% of women leave the tech industry within 10 years? Why are fewer women choosing to pursue computer science and related degrees than ever before? Why have stories of active discouragement, dismissal, harassment, or worse become regular news?

In this talk we’ll examine the causes behind the lack of diversity in our communities, events, and workplaces. We’ll discuss what we can do as community members, event organizers, and co-workers to not only combat this problem, but to encourage positive change by contributing to an atmosphere of inclusivity.

bio: Ashe Dryden is an indie ruby developer living in Madison, WI. She's been involved with the web in some form or another over the course of the past 12 years. Ashe is an outspoken educator for diversity, inclusiveness, and empathy. She's currently writing a book on increasing diversity within companies, as well as working on a video series and site to serve as a resource to people who want to get involved. When she isn't discussing technology or it’s intersection with culture, she's cycling, tweeting, playing board games, debating the social implications of Star Trek episodes, being that awkward girl at the party, and waiting for her next burrito fix.

Small presentation on the Meetup idea and values at 5:45pm by Tyler Zika.

Socializing, forming Master Mind groups, coding, and brainstorming from 6-7pm. Bring your laptop if you want to show what you are working on or you'd like some help.

Another small presentation. Topic and speaker TBA for remainder of Meetup.

RSVP on meetup.com site. Please and thank you.

Happy Coding!

Abstract:

Teaching programming is a hard job. Teaching Haskell is a way harder given its inherent complexity and expectations students have. Nevertheless, there are many approaches to do that. In this talk, I would like to outline the practices that I use and those that I don’t find fruitful. There are quite a few books that can be used for teaching, and I will try to categorize them in terms of their ability to educate a professional Haskell developer. Haskell is a big language, so what should be taught is another crucial question. Should it be a course on functional programming in general or Haskell specifics are fine to teach? For example, there is no clear answer on whether you should attempt teaching something like lenses or stream I/O given limited time. How to teach students about monads? Well, everyone knows the right answer, I will describe my approach. I will also talk about ways to motivate students and to make them learn Haskell by themselves.

Speaker:

Vitaly Bragilevsky, Senior Lecturer at Southern Federal University

Bio:

Vitaly Bragilevsky serves as both the Haskell 2020 Language Committee and the GHC Steering Committee member. He works as a Senior Lecturer at the Southern Federal University in Rostov-on-Don, Russia where he teaches undergraduate students functional programming and theory of computations. He is the author of ‘Haskell in Depth’ (Manning Publications, available via Manning’s early access program).

Recording:

The presentation will be live streamed on our YouTube channel.

Abstract:

The formidable growth of the cyber-threat landscape today is accompanied by an imperative need for providing high-assurance software solutions. In the last decade, binary hardening via In-lined Reference Monitoring (IRMs) has been firmly established as a powerful and versatile technology, providing superior security enforcement for many platforms. IRM frameworks rewrite untrusted binary code, inserting runtime checks to produce safe, self-monitoring code; IRMs are equipped with the ability to enforce a rich set of history-based policies, without requiring access to source code.

In this talk, we present HybridGuard, an IRM framework for hybrid mobile apps. Hybrid mobile frameworks, such as React Native, Ionic, PhoneGap etc., are rapidly becoming the mainstay technology for developing mobile apps. Here, the developer need only write web code, and the framework automatically ports to popular mobile platforms such as Android, iOS etc. While slick, quick, and cost-effective, the exposure of sensitive mobile device resources to web content dramatically increases the attack surface, rendering the apps vulnerable to a slew of dangerous attacks such as code-injection, fracking, cross-site scripting, tapjacking, amongst others.

HybridGuard allows developers fine-grained access control and rich policy enforcement over hybrid mobile apps, protecting against the dangerous vulnerabilities that web code inclusion brings. We will discuss the research challenges and successes on adapting the IRM technology to secure this complex, cross-platform mobile space, and probe into its natural extension into the world of Internet-of-Things.

Bio:

Dr. Meera Sridhar is an Assistant Professor in the Department of Software and Information Systems at UNC Charlotte. Her research interests span language-based and systems security, formal methods, and their application to web, mobile and Internet-of-Things security. Her research is currently supported by the National Science Foundation (NSF). Dr. Sridhar is a member of ACM, ACM-W and WiCyS.

Dr. Sridhar received her Bachelor’s in Computer Science from Carnegie Mellon University in 2002, graduating with University and College Honors. She received her Master’s in Computer Science from Carnegie Mellon University in 2004, and her Ph.D. in Computer Science from The University of Texas at Dallas in 2014. Dr. Sridhar is an International Baccalaureate Diploma holder from the International School Manila, Philippines.

The study of quantum computation has been motivated, in part, by the possibility that quantum computers can perform certain tasks dramatically faster than classical computers. Many of the known quantum-over-classical speedups, such as Shor’s algorithm for factoring integers and Grover’s search algorithm, can be framed as oracle problems or concept learning problems. In one model of concept learning, a student wishes to learn a concept from a teacher by making queries of the teacher. In the interest of efficiency, the student wishes to learn the concept by making as few queries as possible. For any such concept learning problem, there is a corresponding quantum concept learning problem. In the quantum version, the student is allowed to ask a superposition of queries – mathematically, a linear combination of queries – and the teacher answers with the corresponding superposition of the responses. After making this idea precise, we will examine several concept learning problems and their quantum analogues. We will discuss recent joint work with Daniel Copeland (UCSD), in which we show how tools from representation theory can be used to precisely analyze any quantum learning problem with sufficient symmetry.

Will also be streamed live on the Galois YouTube channel: https://www.youtube.com/channel/UC1TJ20iM_dCa0pq6h0tA79w

Abstract: Formal verification has become a well-established part of standard hardware design flows leveraging SAT solvers and model checkers for verification tasks including logical equivalence checking, property checking, and protocol verification. These tools are largely based on all-digital, synchronous, single clock-domain models of hardware behaviour. To address the needs of system-on-chip and multi-core designs, we are developing verification methods for asynchronous, analog, mixed-signal, and mixed-timing circuits.

A key enabling technology for our research is the integration of an SMT solver, Z3, into an interactive theorem prover, ACL2. Our integration, Smtlink, exploits ACL2’s extensive support for reflection: we can write lisp functions that operate on the syntax of pending goals by extracting facts (e.g. function definitions and previously proven theorems) from the ACL2 logical world. Smtlink can automatically translate high-level goals that include user-defined data types and recursive functions into formulas that are in the logic of the SMT solver. We demonstrate the efficacy of this approach with the verification of timed asynchronous handshake circuits and a convergence proof for a digital phase-locked loop.

I will briefly describe related verification work including using automatic differentiation (AD) based algorithms to reason about synchronizers and analog circuits, and interval-arithmetic based verification algorithms to reason about convergence properties of non-linear circuits. Currently, I am working with students and other faculty at UBC to explore verification challenges arising in operating system research, cyber-physical systems, and numerical optimization algorithms used for machine learning.

I gratefully acknowledge my collaborators including Chris Chen, Ian Jones, Matt Kaufmann, Carl Kwan, Yan Peng, Justin Reiher, Mark Schmidt, and Margo Seltzer.

Bio: Mark Greenstreet is a professor in the Department of Computer Science at the University of British Columbia. He earned his B.Sc. (1981) from Caltech, and his MA (1988) and Ph.D. (1992) from Princeton. His research interests span a wide range of formal verification topics, especially any problem, hardware or software, that involves concurrency and/or continuous models. Mark has industrial chip design experience spanning from a design of an FFT chip set for ESL (at TRW subsidiary) in the early 1980’s to work on verifying the synchronizers and clock-domain-crossing circuits in many generations of SPARC CPUs.

Abstract: My talk will present a distributed secure architecture for “cellularization,” a process in which utilities of the players are aligned by credible/non-credible threats. The proposed solution relies on a novel decentralized permissionless cyber-physical architecture that enables players to participate in Information-Asymmetric (Signaling) games, where deception is tamed by costly signaling, formal verification and zero-knowledge cryptography. The signaling, in order to remain honest (e.g., separating), may also involve asymmetric cryptography, crypto-tokens and distributed ledgers. Here, we will present a rough sketch of the architecture and the protocols it involves. Mathematical and computational analyses will appear in a companion paper.

Speaker: Professor Bud Mishra, Courant Institute

Bio: Professor Bud Mishra: An educator, an inventor as well as a mentor to technologists, entrepreneurs and scientists. Prof. Mishra founded the NYU/Courant Bioinformatics Group, a multi-disciplinary group working on research at the interface of computer science, applied mathematics, biology, biomedicine and bio/nano-technologies as well as Tandon-Online program on Bioinformatics Engineering.

Prof. Mishra has industrial experience in Computer and Data Science (aiNexusLab, ATTAP, behold.ai, brainiad, Genesis Media, Pypestream, and Tartan Laboratories), Finance (Instadat, Pattern Recognition Fund, Prospero.ai and Tudor Investment), Robotics and Bio- and Nanotechnologies (Abraxis, Bioarrays, InSilico, MRTech, OpGen and Seqster). He is the author of a textbook on algorithmic algebra and more than two hundred archived publications. He has advised and mentored more than 35 graduate students and post-docs in the areas of computer science, robotics and control engineering, applied mathematics, finance, biology and medicine.

He holds 23 issued and 21 pending patents in areas ranging over robotics, model checking, intrusion detection, cyber security, emergency response, disaster management, data analysis, biotechnology, nanotechnology, genome mapping and sequencing, mutation calling, cancer biology, fintech, adtech, internet architecture and linguistics.

Prof. Mishra’s pioneering work includes: first application of model checking to hardware verification; first robotics technologies for grasping, reactive grippers and work holding; first single molecule genotype/haplotype mapping technology (Optical Mapping); first analysis of copy number variants with a segmentation algorithm, first whole-genome haplotype assembly technology (SUTTA), first clinical-genomic variant/base calling technology (TotalRecaller), first single-molecule single cell nanomapping technology, first non-invasive liquid-biopsy technology, etc.

Prof. Mishra is currently a professor of computer science and mathematics at NYU’s Courant Institute of Mathematical Sciences, professor of engineering at NYUs Tandon School of engineering, professor of human genetics at MSSM Mt. Sinai School of Medicine, visiting scholar in quantitative biology at CSHL Cold Spring Harbor Laboratory and a professor of cell biology at NYU SoM School of Medicine. Prof. Mishra has a degree in Science from Utkal University, in Electronics and Communication Engineering from IIT, Kharagpur, and MS and PhD degrees in Computer Science from Carnegie-Mellon University. He is a fellow of IEEE, ACM, AAAS and EAI, a fellow of National Academy of Inventors (NAI), a Distinguished Alumnus of IIT (Kharagpur), and an NYSTAR Distinguished Professor.

The rise of machine learning (ML) and artificial intelligence (AI) have instigated significant interests in developing domain specific integrated circuits and architectures that can support the computational demands of AI. These chips are commonly known as AI chips. AI chips, both for training and inferencing, have emerged out to be new areas of research and commercialization in semiconductor industry. Particularly, increasing emphasis has been placed on developing low-power AI chips for edge applications where AI can be local, distributed, and seamlessly integrated in sensors or other internet of things (IoT) devices for building naturally-autonomous systems. On the other-hand, globalization of semiconductor ecosystem has led to an era where achieving dominance on Microelectronics supply chain has become as exciting as the famous series “Game of Thrones” for not only the companies but also the countries. Furthermore, the end of Moore’s Law of Scaling of traditional semiconductor transistors has added the climax to this situation as the development and manufacturing of advanced process nodes for the next generation of logic and memory devices get expensive driving most semiconductor industry in the US to be fabless. Interestingly, advanced process nodes such as FINFETS, 3D Transistors, RRAMs/Memristors, and 3D/Monolithic integration and packaging approaches provide unsurpassed opportunities to achieve the much desired On-Chip AI along with the primitives for implementing Hardware Security, and Trust into the integrated circuits. This talk will review some of these technologies and our research efforts in these areas.

The UTxO (unspent transaction output) model is the underlying data structure of Bitcoin, which has since been extended to the Extended UTxO model.

It exists in code, but what does it mean? I will give a novel mathematical model based on some strikingly simple type equations which -- for me at least -- make it easier to see what is structurally going on. I will describe how the equations can be used to obtain two further models, one which is more abstract and one which is more concrete:

• A universal algebra axiomatisation, exhibiting Blockchain as an algebraic structure and so implying a general mathematics and specific testable properties against which to verify an EUTxO implementation, and

• An executable Haskell reference implementation

Increasing set of functionalities, network interoperability, and system design complexity have introduced easily exploitable security vulnerabilities in cyber-physical systems (CPS). Furthermore, the tight interaction between information technology and physical world, as well as the rising levels of autonomy, make these systems vulnerable to attacks beyond the standard cyber-attacks; relying exclusively on conventional security techniques may be unfeasible due to resource-constraints and long system lifetime. Consequently, there is a need to change the way we reason about security in CPS, and start designing platform-aware attack-resilient components and architectures capable providing strong safety and performance guarantees even under attack. In this talk, I will present research challenges and our recent efforts in this domain, starting from cyber-physical security techniques that (a) capture effects of attacks on system performance, (b) introduce attack-resilience into components at each level of the autonomy stack, and (c) enable mapping of the desired Quality-of-Control (QoC) under attack guarantees into real-time platform requirements in way that supports design-time tradeoffs between the QoC under attack and security-related overhead. For systems with varying levels of autonomy and human interaction, I will also show how we can exploit human power of inductive reasoning and the ability to provide context, to improve the overall security guarantees. Finally, I will present how we can capture security-related CPS specification as hyperproperties, and introduce statistical model checking methods to check such specifications.

In the real world, people join humanity, grow up trusting very different quorums from one another, and they may change their quorums with time. In technical terms we could call this an open permissionless system with mutable local quorums.

One might expect such a system to be a jumbled disorder — and yet, somehow, it self-organises into uniform areas of fairly stable consensus. One might almost suspect there could be some deep mathematical principles involved!

In this talk I will discuss consensus in a permissionless open system with mutable local quorums, and show how a topological view of the system gives a clean mathematical analysis with surprisingly good explanatory power.

Secure multi-party computation (MPC) allows multiple parties, each holding private data that they are unwilling to share, to collaborate to perform computations over their data, while revealing nothing other than the result. The theory behind secure computation is already 35 years old, but in the last 15 years researchers in the field have demonstrated tremendous improvement in performance. Today, a confluence of factors are driving an increased interest in secure computation, both in the public domain and in industry, including the advancements in MPC mentioned above, the explosion in the volume of private user data being generated, and the advancements in machine learning that are being deployed to leverage that private data.

In this talk, I will give an overview of several of my recent results that has helped scale the performance of secure computation. In the first half of the talk, I will focus on the setting where we have large volumes of data and a secure computation that is out-source to a small number of servers — the Few-PC setting. I will focus on a security relaxation that allows us to improve communication costs asymptotically and concretely for a large class of computations. In the second half of the talk, I will describe several results that allow us to scale MPC to thousands or even millions of parties, by demonstrating a protocol that requires less communication and computation from each participant as the number of participants grows.