Magnus Madsen

I am an assistant professor at the Department of Computer Science in the Database, Programming, and Web Technologies group at Aalborg University. I was previously a postdoctoral researcher at the University of Waterloo in the Programming Languages Group under the supervision of Ondřej Lhoták. I received my PhD from Aarhus University for the thesis Static Analysis of Dynamic Languages. My thesis adviser was Anders Møller.

My full curriculum vitae. My Google Scholar. My DBLP. My GitHub.

My email is my first name at cs.aau.dk.

My primary research interests are in programming language design, compilers, and program analysis.

Research Projects

The Flix Language and Compiler

Flix is a statically typed functional- and logic programming language inspired by Scala, OCaml, F#, Haskell, and Datalog. The syntax of Flix resembles Scala and Datalog. The type system supports local type inference and is based on Hindley-Milner. Flix runs on the Java Virtual Machine and compiles directly to JVM bytecode.

Flix supports hybrid functional and logic programming featuring a built-in fixed point engine based on semi-naive evaluation. The functional and logic languages can be used independently, if so desired. For example, a Flix program can be purely functional, or Flix can be used as a standalone Datalog engine.

Papers related to this line of research include:

Peer-Reviewed Publications

  • A Model for Reasoning About JavaScript Promises (OOPSLA '17)

    Magnus Madsen, Ondřej Lhoták, Frank Tip

    In JavaScript programs, asynchrony arises in situations such as web-based user-interfaces, communicating with servers through HTTP requests, and non-blocking I/O. Event-based programming is the most popular approach for managing asynchrony, but suffers from problems such as lost events and event races, and results in code that is hard to understand and debug. Recently, ECMAScript 6 has added support for promises, an alternative mechanism for managing asynchrony that enables programmers to chain asynchronous computations while supporting proper error handling. However, promises are complex and error-prone in their own right, so programmers would benefit from techniques that can reason about the correctness of promise-based code.

    Since the ECMAScript 6 specification is informal and intended for implementers of JavaScript engines, it does not provide a suitable basis for formal reasoning. This paper presents lambda_p, a core calculus that captures the essence of ECMAScript 6 promises. Based on lambda_p, we introduce the promise graph, a program representation that can assist programmers with debugging of promise-based code. We then report on a case study in which we investigate how the promise graph can be helpful for debugging errors related to promises in code fragments posted to the StackOverflow website.

    Paper BibTex
  • From Datalog to Flix: A Declarative Language for Fixed Points on Lattices (PLDI '16)

    Magnus Madsen, Ming-Ho Yee, Ondřej Lhoták

    We present Flix, a declarative programming language for specifying and solving least fixed point problems, particularly static program analyses. Flix is inspired by Datalog and extends it with lattices and monotone functions. Using Flix, implementors of static analyses can express a broader range of analyses than is currently possible in pure Datalog, while retaining its familiar rule-based syntax.

    We define a model-theoretic semantics of Flix asa natural extension of the Datalog semantics. This semantics captures the declarative meaning of Flix programs without imposing any specific evaluation strategy. An efficient strategy is semi-naive evaluation which we adapt for Flix. We have implemented a compiler and runtime for Flix, and used it to express several well-known static analyses, including the IFDS and IDE algorithms. The declarative nature of Flix clearly exposes the similarity between these two algorithms.

    Paper BibTex Website
  • Feedback-Directed Instrumentation for Deployed JavaScript Applications (ICSE '16)

    Magnus Madsen, Frank Tip, Esben Andreasen, Koushik Sen, Anders Møller

    Many bugs in JavaScript applications manifest themselves as objects that have incorrect property values when a failure occurs. For this type of error, stack traces and log files are often insufficient for diagnosing problems. In such cases, it is helpful for developers to know the control flow path from the creation of an object to a crashing statement. Such crash paths are useful for understanding where the object originated and whether any properties of the object were corrupted since its creation.

    We present a feedback-directed instrumentation technique for computing crash paths that allows the instrumentation overhead to be distributed over a crowd of users and to reduce it for users who do not encounter the crash. We implemented our technique in a tool, Crowdie, and evaluated it on 10 real-world issues for which error messages and stack traces are insufficient to isolate the problem. Our results show that feedback-directed instrumentation requires 5% to 25% of the program to be instrumented, that the same crash must be observed 3 to 10 times to discover the crash path, and that feedback-directed instrumentation typically slows down execution by a factor 2x–9x compared to 8x–90x for an approach where applications are fully instrumented.

    Paper BibTex
  • Static Analysis of Event-Driven Node.js JavaScript Applications (OOPSLA '15)

    Magnus Madsen, Frank Tip, Ondřej Lhoták

    Many JavaScript programs are written in an event-driven style. In particular, in server-side Node.js applications, operations involving sockets, streams, and files are typically performed in an asynchronous manner, where the execution of listeners is triggered by events. Several types of programming errors are specific to such event-based programs (e.g., unhandled events, and listeners that are registered too late). We present the event-based call graph, a program representation that can be used to detect bugs related to event handling. We have designed and implemented three analyses for constructing event-based call graphs. Our results show that these analyses are capable of detecting problems reported on StackOverflow. Moreover, we show that the number of false positives reported by the analysis on a suite of small Node.js applications is manageable.

    Paper BibTex
  • Sparse Dataflow Analysis with Pointers and Reachability (SAS '14)

    Magnus Madsen, Anders Møller

    Many static analyzers exploit sparseness techniques to reduce the amount of information being propagated and stored during analysis. Although several variations are described in the literature, no existing technique is suitable for analyzing JavaScript code. In this paper, we point out the need for a sparse analysis framework that supports pointers and reachability. We present such a framework, which uses static single assignment form for heap addresses and computes def-use information on-the-fly. We also show that essential information about dominating definitions can be maintained efficiently using quadtrees. The framework is presented as a systematic modification of a traditional dataflow analysis algorithm.

    Our experimental results demonstrate the effectiveness of the technique for a suite of JavaScript programs. By also comparing the performance with an idealized staged approach that computes pointer information with a pre-analysis, we show that the cost of computing def-use information on-the-fly is remarkably small.

    Paper BibTex
  • String Analysis for Dynamic Field Access (CC '14)

    Magnus Madsen, Esben Andreasen

    In JavaScript, and scripting languages in general, dynamic field access is a commonly used feature. Unfortunately, current static analysis tools either completely ignore dynamic field access or use overly conservative approximations that lead to poor precision and scalability. We present new string domains to reason about dynamic field access in a static analysis tool. A key feature of the domains is that the equal, concatenate and join operations take O(1) time.

    Experimental evaluation on four common JavaScript libraries, including jQuery and Prototype, shows that traditional string domains are insufficient. For instance, the commonly used constant string domain can only ensure that at most 21% dynamic field accesses are without false positives. In contrast, our string domain H ensures no false positives for up to 90% of all dynamic field accesses.

    We demonstrate that a dataflow analysis equipped with the H domain gains significant precision resulting in an analysis speedup of more than 1.5x for 7 out of 10 benchmark programs.

    Paper BibTex
  • Practical Static Analysis of JavaScript Applications in the Presence of Frameworks and Libraries (FSE/ESEC '13)

    Magnus Madsen, Benjamin Livshits, Michael Fanning

    JavaScript is a language that is widely-used for both web- based and standalone applications such as those in the Windows 8 operating system. Analysis of JavaScript has long been known to be challenging due to the language’s dynamic nature. On top of that, most JavaScript applications rely on large and complex libraries and frameworks, often written in a combination of JavaScript and native code such as C and C++. Stubs have been commonly employed as a partial specification mechanism to address the library problem; alas, they are tedious and error-prone.

    However, the manner in which library code is used within applications often sheds light on what library APIs return or pass into callbacks declared within the application. In this paper, we propose a technique which combines pointer analysis with a novel use analysis to handle many challenges posed by large JavaScript libraries. Our techniques have been implemented and empirically validated on a set of 25 Windows 8 JavaScript applications, averaging 1,587 lines of code, together with about 30,000 lines of library code, demonstrating a combination of scalability and precision

    Paper BibTex
  • Modeling the HTML DOM and Browser API in Static Analysis of JavaScript Web Applications (FSE/ESEC '11)

    Simon Holm Jensen, Magnus Madsen, Anders Møller

    Developers of JavaScript web applications have little tool support for catching errors early in development. In comparison, an abundance of tools exist for statically typed languages, including sophisticated integrated development environments and specialized static analyses. Transferring such technologies to the domain of JavaScript web applications is challenging. In this paper, we discuss the challenges, which include the dynamic aspects of JavaScript and the complex interactions between JavaScript, HTML, and the browser. From this, we present the first static analysis that is capable of reasoning about the flow of control and data in modern JavaScript applications that interact with the HTML DOM and browser API.

    One application of such a static analysis is to detect type- related and dataflow-related programming errors. We report on experiments with a range of modern web applications, including Chrome Experiments and IE Test Drive applications, to measure the precision and performance of the technique. The experiments indicate that the analysis is able to show absence of errors related to missing object properties and to identify dead and unreachable code. By measuring the precision of the types inferred for object properties, the analysis is precise enough to show that most expressions have unique types. By also producing precise call graphs, the analysis additionally shows that most invocations in the programs are monomorphic. We furthermore study the usefulness of the analysis to detect spelling errors in the code. Despite the encouraging results, not all problems are solved and some of the experiments indicate a potential for improvement, which allows us to identify central remaining challenges and outline directions for future work.

    Paper BibTex

Workshop and Other Publications

  • Programming a Dataflow Analysis in Flix (TAPAS '16)

    Magnus Madsen, Ming-Ho Yee, Ondřej Lhoták

    Flix is a logic and functional language designed for the implementation of static analysis tools. Flix is inspired by Datalog and extends it with user-defined lattices as well as monotone filter and transfer functions. In recent work, Flix has been used to express several analyses, including the Strong Update analysis, and the IFDS and IDE algorithms

    Paper BibTex