Search

Fortran is still widely used in scientific computing, and a very large corpus of legacy as well as new code is written in FORTRAN 77. In general this code is not type safe, so that incorrect programs can compile without errors. In this paper, we present a formal approach to ensure type safety of legacy Fortran code through automated program transformation. The objective of this work is to reduce programming errors by guaranteeing type safety. We present the first rigorous analysis of the type safety of FORTRAN 77 and the novel program transformation and type checking algorithms required to convert FORTRAN 77 subroutines and functions into pure, side-effect free subroutines and functions in Fortran 90. We have implemented these algorithms in a source-to-source compiler which type checks and automatically transforms the legacy code. We show that the resulting code is type safe and that the pure, side-effect free and referentially transparent subroutines can readily be offloaded to accelerators.

International audience; Due to the rise of AI applications, machine learning (ML) libraries, often written in Python, have become far more accessible. ML libraries tend to be updated periodically, which may deprecate existing APIs, making it necessary for application developers to update their usages. In this paper, we build a tool to automate deprecated API usage updates. We first present an empirical study to better understand how updates of deprecated ML API usages in Python can be done. The study involves a dataset of 112 deprecated APIs from Scikit-Learn, TensorFlow, and PyTorch. Guided by the findings of our empirical study, we propose MLCatchUp, a tool to automate the updates of Python deprecated API usages, that automatically infers the API migration transformation through comparison of the deprecated and updated API signatures. These transformations are expressed in a Domain Specific Language (DSL). We evaluate MLCatchUp using a dataset containing 267 files with 551 API usages that we collected from public GitHub repositories. In our dataset, MLCatchUp can detect deprecated API usages with perfect accuracy, and update them correctly for 80.6% of the cases. We further improve the accuracy of MLCatchUp in performing updates by adding a feature that allows it to accept an additional user input that specifies the transformation constraints in the DSL for context-dependent API migration. Using this addition, MLCatchUp can make correct updates for 90.7% of the cases.

Tool Paper; International audience; Machine learning (ML) libraries are gaining vast popularity, especially in the Python programming language. Using the latest version of such libraries is recommended to ensure the best performance and security. When migrating to the latest version of a machine learning library, usages of deprecated APIs need to be updated, which is a time-consuming process. In this paper, we propose MLCatchUp, an automated API usage update tool for deprecated APIs of popular ML libraries written in Python. MLCatchUp automatically infers the required transformation to migrate usages of deprecated API through the differences between the deprecated and updated API signatures. MLCatchUp offers a readable transformation rule in the form of a domain specific language (DSL). We evaluate MLCatchUp using a dataset of 267 real-world Python code containing 551 usages of 68 distinct deprecated APIs, where MLCatchUp achieves 90.7% accuracy. A video demonstration of MLCatchUp is available at https://youtu.be/5NjOPNt5iaA.

When working with a document, users often perform context-specific repetitive edits – changes to the document that are similar but specific to the contexts at their locations. Programming by demonstration/examples (PBD/PBE) systems automate these tasks by learning programs to perform the repetitive edits from demonstration or examples. However, PBD/PBE systems are not widely adopted, mainly because they require modal UIs – users must enter a special mode to give the demonstration/examples. This paper presents Blue-Pencil, a modeless system for synthesizing edit suggestions on the fly. Blue-Pencil observes users as they make changes to the document, silently identifies repetitive changes, and automatically suggests transformations that can apply at other locations. Blue-Pencil is parameterized – it allows the ”plug-and-play” of different PBE engines to support different document types and different kinds of transformations. We demonstrate this parameterization by instantiating Blue-Pencil to several domains – C# and SQL code, markdown documents, and spreadsheets – using various existing PBE engines. Our evaluation on 37 code editing sessions shows that Blue-Pencil synthesized edit suggestions with a precision of 0.89 and a recall of 1.0, and took 199 ms to return suggestions on average. Finally, we report on several improvements based on feedback gleaned from a field study with professional programmers to investigate the use of Blue-Pencil during long code editing sessions. Blue-Pencil has been integrated with Visual Studio IntelliCode to power the IntelliCode refactorings feature.

Improving the performance of deep neural networks (DNNs) is important to both the compiler and neural architecture search (NAS) communities. Compilers apply program transformations in order to exploit hardware parallelism and memory hierarchy. However, legality concerns mean they fail to exploit the natural robustness of neural networks. In contrast, NAS techniques mutate networks by operations such as the grouping or bottlenecking of convolutions, exploiting the resilience of DNNs. In this work, we express such neural architecture operations as program transformations whose legality depends on a notion of representational capacity. This allows them to be combined with existing transformations into a unified optimization framework. This unification allows us to express existing NAS operations as combinations of simpler transformations. Crucially, it allows us to generate and explore new tensor convolutions. We prototyped the combined framework in TVM and were able to find optimizations across different DNNs, that significantly reduce inference time - over 3$\times$ in the majority of cases. Furthermore, our scheme dramatically reduces NAS search time. Code is available at~\href{https://github.com/jack-willturner/nas-as-program-transformation-exploration}{this https url}.

Mixed Boolean-Arithmetic (MBA) expression mixes bitwise operations (e.g., AND, OR, and NOT) and arithmetic operations (e.g., ADD and IMUL). It enables a semantic-preserving program transformation to convert a simple expression to a difficult-to-understand but equivalent form. MBA expression has been widely adopted as a highly effective and low-cost obfuscation scheme. However, state-of-the-art deobfuscation research proposes substantial challenges to the MBA obfuscation technique. Attacking methods such as bit-blasting, pattern matching, program synthesis, deep learning, and mathematical transformation can successfully simplify specific categories of MBA expressions. Existing MBA obfuscation must be enhanced to overcome these emerging challenges.

Developers frequently change the type of a program element and update all its references for performance, security, concurrency,library migration, or better maintainability. Despite type changes being a common program transformation, it is the least automated and the least studied. With this knowledge gap, researchers miss opportunities to improve the state of the art in automation for software evolution, tool builders do not invest resources where automation is most needed, language and library designers can-not make informed decisions when introducing new types, and developers fail to use common practices when changing types. To fill this gap, we present the first large-scale and most fine-grained empirical study on type changes in Java. We develop state-of-the-art tools to statically mine 297,543 type changes and their subsequent code adaptations from a diverse corpus of 129 Java projects containing 416,652 commits. With this rich data set we answer research questions about the practice of type changes. Among others, we found that type changes are actually more common than renaming,but the current research and tools for type changes are inadequate.Based on our extensive and reliable data, we present actionable,empirically-justified implications.

Models’ transformations involve code abstraction and program description, i.e., models’ transformations (MTs) operate in a more diverse set of artifacts than program transformation. Note that MTs allow programmers to link different structures, as Category Theory does for Mathematics, through recognizing similar features and properties. In this paper, we show that Category Theory can be used to describe MTs. Specifically, we propose a categorical framework for transforming a semi-structured data model, an OEM database, into a model of structured data, in UML language. This categorical approach allows us to establish a bridge between such models and the categories of simple and directed graphs, which makes it possible to apply the features of such categories to manage databases.

The problem of determining whether or not any program terminates was shown to be undecidable by Turing, but recent advances in the area have allowed this information to be determined for a large class of programs. The classic method for deciding whether a program terminates dates back to Turing himself and involves finding a ranking function that maps a program state to a well-order, and then proving that the result of this function decreases for every possible program transition. More recent approaches to proving termination have involved moving away from the search for a single ranking function and toward a search for a set of ranking functions; this set is a choice of ranking functions and a disjunctive termination argument is used. In this paper, we describe a new technique for determining whether programs terminate. Our technique is applied to the output of the distillation program transformation that converts programs into a simplified form called distilled form. Programs in distilled form are converted into a corresponding labelled transition system and termination can be demonstrated by showing that all possible infinite traces through this labelled transition system would result in an infinite descent of well-founded data values. We demonstrate our technique on a number of examples, and compare it to previous work., In Proceedings VPT/HCVS 2020, arXiv:2008.02483. This work owes a lot to the input of Neil Jones, who provided many useful insights and ideas on the subject matter presented here

When a program is executed on a untrusted cloud, the confidentiality of the program logic and related control flow variables should be protected. To obtain this goal, control flow obfuscation can be used. However, previous work has not been effective in terms of performance overhead and security. In this paper, we propose E-CFHider, a hardware-based method to protect the confidentiality of logics and variables involved in control flow. By using the Intel SGX technology and program transformation, we store the control flow variables and execute statements related to those variables in the trusted execution environment, i.e., the SGX enclave. We found this method can better protect the confidentiality of control flow and achieve acceptable performance overhead.

Static analysis is a proven technique for catching bugs during software development. However, analysis tooling must approximate, both theoretically and in the interest of practicality. False positives are a pervading manifestation of such approximations---tool configuration and customization is therefore crucial for usability and directing analysis behavior. To suppress false positives, developers readily disable bug checks or insert comments that suppress spurious bug reports. Existing work shows that these mechanisms fall short of developer needs and present a significant pain point for using or adopting analyses. We draw on the insight that an analysis user always has one notable ability to influence analysis behavior regardless of analyzer options and implementation: modifying their program. We present a new technique for automated, generic, and temporary code changes that tailor to suppress spurious analysis errors. We adopt a rule-based approach where simple, declarative templates describe general syntactic changes for code patterns that are known to be problematic for the analyzer. Our technique promotes program transformation as a general primitive for improving the fidelity of analysis reports (we treat any given analyzer as a black box). We evaluate using five different static analyzers supporting three different languages (C, Java, and PHP) on large, real world programs (up to 800KLOC). We show that our approach is effective in sidestepping long-standing and complex issues in analysis implementations.

This work considers the trade-off between security and performance when revealing partial information about encrypted data computed on. The focus of our work is on information revealed through control flow side-channels when executing programs on encrypted data. We use quantitative information flow to measure security, running time to measure performance and program transformation techniques to alter the trade-off between the two. Combined with information flow policies, we perform a policy-aware security and performance trade-off (PASAPTO) analysis. We formalize the problem of PASAPTO analysis as an optimization problem, prove the NPhardness of the corresponding decision problem and present two algorithms solving it heuristically.We implemented our algorithms and combined them with the Dataflow Authentication (DFAuth) approach for outsourcing sensitive computations. Our DFAuth Trade-off Analyzer (DFATA) takes Java Bytecode operating on plaintext data and an associated information flow policy as input. It outputs semantically equivalent program variants operating on encrypted data which are policy-compliant and approximately Pareto-optimal with respect to leakage and performance. We evaluated DFATA in a commercial cloud environment using Java programs, e.g., a decision tree program performing machine learning on medical data. The decision tree variant with the worst performance is 357% slower than the fastest variant. Leakage varies between 0% and 17% of the input.

Distributed applications enhance their execution by using remote resources. However, distributed execution incurs communication, synchronization, fault-handling, and security overheads. If these overheads are not offset by the yet larger execution enhancement, distribution becomes counterproductive. For maximum benefits, the distribution's granularity cannot be too fine or too crude; it must be just right. In this paper, we present a novel approach to re-architecting distributed applications, whose distribution granularity has turned ill-conceived. To adjust the distribution of such applications, our approach automatically reshapes their remote invocations to reduce aggregate latency and resource consumption. To that end, our approach insources a remote functionality for local execution, splits it into separate functions to profile their performance, and determines the optimal redistribution based on a cost function. Redistribution strategies combine separate functions into single remotely invocable units. To automate all the required program transformations, our approach introduces a series of domain-specific automatic refactorings. We have concretely realized our approach as an analysis and automatic program transformation infrastructure for the important domain of full-stack JavaScript applications, and evaluated its value, utility, and performance on a series of real-world cross-platform mobile apps. Our evaluation results indicate that our approach can become a useful tool for software developers charged with the challenges of re-architecting distributed applications.

Type systems are useful not just for the safety guarantees they provide, but also for helping compilers generate more efficient code by simplifying important program analyses. In Rust, the type system imposes a strict discipline on pointer aliasing, and it is an express goal of the Rust compiler developers to make use of that alias information for the purpose of program optimizations that reorder memory accesses. The problem is that Rust also supports unsafe code, and programmers can write unsafe code that bypasses the usual compiler checks to violate the aliasing discipline. To strike a balance between optimizations and unsafe code, the language needs to provide a set of rules such that unsafe code authors can be sure, if they are following these rules, that the compiler will preserve the semantics of their code despite all the optimizations it is doing. In this work, we propose Stacked Borrows , an operational semantics for memory accesses in Rust. Stacked Borrows defines an aliasing discipline and declares programs violating it to have undefined behavior , meaning the compiler does not have to consider such programs when performing optimizations. We give formal proofs (mechanized in Coq) showing that this rules out enough programs to enable optimizations that reorder memory accesses around unknown code and function calls, based solely on intraprocedural reasoning. We also implemented this operational model in an interpreter for Rust and ran large parts of the Rust standard library test suite in the interpreter to validate that the model permits enough real-world unsafe Rust code.

© 2020 Copyright held by the owner/author(s). One of the workhorse techniques for implementing bottom-up Datalog engines is seminaïve evaluation. This optimization improves the performance of Datalog's most distinctive feature: recursively defined predicates. These are computed iteratively, and under a naïve evaluation strategy, each iteration recomputes all previous values. Seminaïve evaluation computes a safe approximation of the difference between iterations. This can asymptotically improve the performance of Datalog queries. Seminaïve evaluation is defined partly as a program transformation and partly as a modified iteration strategy, and takes advantage of the first-order nature of Datalog code. This paper extends the seminaïve transformation to higher-order programs written in the Datafun language, which extends Datalog with features like first-class relations, higher-order functions, and datatypes like sum types.

Inversion is an important and useful program transformation and has been studied in various programming language paradigms. Semi-inversion is more general than just swapping the input and output of a program; instead, parts of the input and output can be freely swapped. In this paper, we present a polyvariant semi-inversion algorithm for conditional constructor term rewriting systems. These systems can model logic and functional languages, which have the advantage that semi-inversion, as well as partial and full inversion, can be studied across different programming paradigms. The semi-inverter makes use of local inversion and a simple but effective heuristic and is proven to be correct. A Prolog implementation is applied to several problems, including inversion of a simple encrypter and of a program inverter for a reversible language.

Backpropagation is a classic automatic differentiation algorithm computing the gradient of functions specified by a certain class of simple, first-order programs, called computational graphs. It is a fundamental tool in several fields, most notably machine learning, where it is the key for efficiently training (deep) neural networks. Recent years have witnessed the quick growth of a research field called differentiable programming, the aim of which is to express computational graphs more synthetically and modularly by resorting to actual programming languages endowed with control flow operators and higher-order combinators, such as map and fold. In this paper, we extend the backpropagation algorithm to a paradigmatic example of such a programming language: we define a compositional program transformation from the simply-typed lambda-calculus to itself augmented with a notion of linear negation, and prove that this computes the gradient of the source program with the same efficiency as first-order backpropagation. The transformation is completely effect-free and thus provides a purely logical understanding of the dynamics of backpropagation., Comment: 27 pages

Compiler optimizations may break or weaken the security properties of a source program. This work develops a translation validation methodology for secure compilation. A security property is expressed as an automaton operating over a bundle of program traces. A refinement proof scheme derived from a property automaton guarantees that the associated security property is preserved by a program transformation. This generalizes known refinement methods that apply only to specific security properties. In practice, the refinement relations (“security witnesses”) are generated during compilation and validated independently with a refinement checker. This process is illustrated for common optimizations. Crucially, it is not necessary to formally verify the compiler implementation, which is infeasible for production compilers.

We present a new approach for building source-to-source transformations that can run on multiple programming languages, based on a new way of representing programs called incremental parametric syntax. We implement this approach in Haskell in our Cubix system, and construct incremental parametric syntaxes for C, Java, JavaScript, Lua, and Python. We demonstrate a whole-program refactoring tool that runs on all of them, along with three smaller transformations that each run on several. Our evaluation shows that (1) once a transformation is written, little work is required to configure it for a new language (2) transformations built this way output readable code which preserve the structure of the original, according to participants in our human study, and (3) our transformations can still handle language corner-cases, as validated on compiler test suites.

An improvement is a correct program transformation that optimizes the program, where the criterion is that the number of computation steps until a value is obtained is not strictly increased in any context. This paper investigates improvements in both – an untyped and a polymorphically typed variant – of a call-by-need lambda calculus with letrec, case, constructors and seq. Besides showing that several local transformations are optimizations, a main result of this paper is a proof that common subexpression elimination is correct and an improvement, which proves a conjecture and thus closes a gap in the improvement theory of Moran and Sands. The improvement relation used in this paper is generic in which essential computation steps are counted and thus the obtained results apply for several notions of improvement. Besides the small-step operational semantics, also an abstract machine semantics is considered for counting computation steps. We show for several length measures that the call-by-need calculus of Moran and Sands and our calculus are equivalent.

We extend a technique called Compiling Control. The technique transforms coroutining logic programs into logic programs that, when executed under the standard left-to-right selection rule (and not using any delay features) have the same computational behavior as the coroutining program. In recent work, we revised Compiling Control and reformulated it as an instance of Abstract Conjunctive Partial Deduction. This work was mostly focused on the program analysis performed in Compiling Control. In the current paper, we focus on the synthesis of the transformed program. Instead of synthesizing a new logic program, we synthesize a CHR(Prolog) program which mimics the coroutining program. The synthesis to CHR yields programs containing only simplification rules, which are particularly amenable to certain static analysis techniques. The programs are also more concise and readable and can be ported to CHR implementations embedded in other languages than Prolog., In Proceedings VPT 2017, arXiv:1708.06887

We present a tool, simplify-defun, that transforms the definition of a given function into a simplified definition of a new function, providing a proof checked by ACL2 that the old and new functions are equivalent. When appropriate it also generates termination and guard proofs for the new function. We explain how the tool is engineered so that these proofs will succeed. Examples illustrate its utility, in particular for program transformation in synthesis and verification., Comment: In Proceedings ACL2Workshop 2017, arXiv:1705.00766

International audience; Skeletal parallelism is a model of parallelism where parallel constructs are provided to the programmer as usual patterns of parallel algorithms. High-level skeleton libraries often offer a global view of programs instead of the common Single Program Multiple Data view in parallel programming. A program is written as a sequential program but operates on parallel data structures. Most of the time, skeletons on a parallel data structure have counterparts on a sequential data structure. For example, the map function that applies a given function to all the elements of a sequential collection (e.g., a list) has a map skeleton counterpart that applies a sequential function to all the elements of a distributed collection. Two of the challenges a programmer faces when using a skeleton library that provides a wide variety of skeletons are: which are the skeletons to use, and how to compose them? These design decisions may have a large impact on the performance of the parallel programs. However, skeletons, especially when they do not mutate the data structure they operate on, but are rather implemented as pure functions , possess algebraic properties that allow to transform compositions of skeletons into more efficient compositions of skeletons. In this paper, we present such an automatic transformation framework for the Python skeleton library PySke and evaluate it on several example applications.

Big Data systems are typically implemented in object-oriented languages such as Java and Scala due to the quick development cycle they provide. These systems are executed on top of a managed runtime such as the Java Virtual Machine (JVM), which requires each data item to be represented as an object before it can be processed. This representation is the direct cause of many kinds of severe inefficiencies. We developed Gerenuk, a compiler and runtime that aims to enable a JVM-based data-parallel system to achieve near-native efficiency by transforming a set of statements in the system for direct execution over inlined native bytes. The key insight leading to Gerenuk's success is two-fold: (1) analytics workloads often use immutable and confined data types. If we speculatively optimize the system and user code with this assumption, the transformation can be made tractable. (2) The flow of data starts at a deserialization point where objects are created from a sequence of native bytes and ends at a serialization point where they are turned back into a byte sequence to be sent to the disk or network. This flow naturally defines a speculative execution region (SER) to be transformed. Gerenuk compiles a SER speculatively into a version that can operate directly over native bytes that come from the disk or network. The Gerenuk runtime aborts the SER execution upon violations of the immutability and confinement assumption and switches to the slow path by deserializing the bytes and re-executing the original SER. Our evaluation on Spark and Hadoop demonstrates promising results.

Cloud computing allows clients uploading their sensitive data to the public cloud and perform sensitive computations in those untrusted areas, which drives to possible violations to the confidentiality of client sensitive data. By leveraging the program transformation and the Intel Software Guard Extension (SGX) technology, our proposed solution hides the security-sensitive statements inside an SGX enclave. Some former works have shown that most applications can run in their entirety inside trusted areas such as SGX enclaves, and that leads to a large trusted computing base (TCB). As a result, we analyze a case study in which we partition an application and use an SGX enclave to protect only security-sensitive statements, thus obtaining a smaller TCB. In this paper, we describe our case study that secures applications written in Java using Intel SGX technology. We analyzed our proposed solution using concrete examples to show how the confidentiality of security-sensitive variables is protected.

In this paper, we show how stream fusion, a program transformation technique used in functional programming, can be adapted for an Object-Oriented setting. This makes it possible to have more Stream operators than the ones currently provided by the Java Stream API. The addition of more operators allows for a greater deal of expressiveness. To this extent, we show how these operators are incorporated in the stream setting. Furthermore, we also demonstrate how a specific set of optimizations eliminates overheads and produces equivalent code in the form of for loops. In this way, programmers are relieved from the burden of writing code in such a cumbersome style, thus allowing for a more declarative and intuitive programming approach., This work is financed by the ERDF European Regional Development Fund through the Operational Programme for Competitiveness and Internationalisation - COMPETE 2020 Programme and by National Funds through the Portuguese funding agency, FCT - Fundação para a Ciência e a Tecnologia within project POCI-01-0145-FEDER016718.

Static code analysis tools such as FindBugs and SonarQube are widely used on open-source and industrial projects to detect a variety of issues that may negatively affect the quality of software. Despite these tools' popularity and high level of automation, several empirical studies report that developers normally fix only a small fraction (typically, less than 10% [1]) of the reported issues—so-called "warnings". If these analysis tools could also automatically provide suggestions on how to fix the issues that trigger some of the warnings, their feedback would become more actionable and more directly useful to developers. In this work, we investigate whether it is feasible to automatically generate fix suggestions for common warnings issued by static code analysis tools, and to what extent developers are willing to accept such suggestions into the codebases they're maintaining. To this end, we implemented a Java program transformation technique that fixes 11 distinct rules checked by two well-known static code analysis tools (SonarQube and SpotBugs). Fix suggestions are generated automatically based on templates, which are instantiated in a way that removes the source of the warnings; templates for some rules are even capable of producing multi-line patches. We submitted 38 pull requests, including 920 fixes generated automatically by our technique for various open-source Java projects, including the Eclipse IDE and both SonarQube and SpotBugs tools. At the time of writing, project maintainers accepted 84% of our fix suggestions (95% of them without any modifications). These results indicate that our approach to generating fix suggestions is feasible, and can help increase the applicability of static code analysis tools.

The Static Single Assignment (SSA) form is an intermediate representation used for the analysis and optimization of programs in modern compilers. The ϕ-function placement is the most computationally expensive part of converting any program into its SSA form. The most widely-used ϕ-function placement algorithms are based on computing dominance frontiers. However, this kind of algorithms works under the limiting assumption that all variables are defined at the beginning of the program, which is not the case for local variables. In this paper, we introduce an innovative algorithm based on computing reaching definitions, only assuming that global variables and formal parameters are defined at the beginning of the program. We implemented our algorithm and compared it to a well-known dominance frontiers-based algorithm in the Clang/LLVM compiler framework by performing experiments on a benchmarking suite for Perl. The results of our experiments show that, besides a few computationally expensive cases, our algorithm is fairly efficient, and most notably it produces up to 169% and on an average 74% fewer ϕ-functions than the reference dominance frontiers-based algorithm.

Deprecation of APIs in software libraries is common when library maintainers make changes to a library and will no longer support certain APIs in the future. When deprecation occurs, developers whose programs depend on the APIs need to replace the usages of the deprecated APIs sooner or later. Often times, software documentation specifies which new APIs the developers should use in place of a deprecated API. However, replacing the usages of a deprecated API remains a challenge since developers may not know exactly how to use the new APIs. The developers would first need to understand the API changes before they can replace the deprecated API correctly. Previous work has proposed an approach to assist developers in deprecatedAndroid API replacement by learning from examples. In this work, we also focus on Android APIs and propose an approach named No Example API Transformation (NEAT) to generate transformation rules that can assist developers in deprecatedAPI replacement even when code examples are not available (e.g., when the deprecation has happened recently). We have validated the effectiveness of NEATon generating transformation rules for deprecated Android APIs. Using NEAT, we can generate 37 transformation rules for 37 out of a selection of 100 deprecatedAPIs and have validated these rules to be correct.

When a program is executed on an untrusted cloud, the confidentiality of the program's logics needs to be protected. Control flow obfuscation is a direct approach to obtain this goal. However, existing methods in this direction cannot achieve both high confidentiality and low overhead. In this paper, we propose CFHider, a hardware-assisted method to protect the control flow confidentiality. By combining program transformation and Intel Software Guard Extension (SGX) technology, CFHider moves branch statement conditions to an opaque and trusted memory space, i.e., the enclave, thereby offering a guaranteed control flow confidentiality. Based on the design of CFHider, we developed a prototype system targeting on Java applications. Our analysis and experimental results indicate that CFHider is effective in protecting the control flow confidentiality and incurs a much reduced performance overhead than existing software-based solutions (by a factor of 8.8).

Malicious reverse engineering is a problem when a program is delivered to the end users. In fact, an end user might try to understand the internals of the program, in order to elaborate an attack, tamper with the software and alter its behaviour. Code obfuscation represents a mitigation to these kind of malicious reverse engineering and tampering attacks, making programs harder to analyze (by a tool) and understand (by a human). In this paper, we present Oblive, a tool meant to support developers in applying code obfuscation to their programs. A developer is required to specify security requirements as single-line code annotations only. Oblive, then, reads annotations and applies state-of-the-art data and code obfuscation, namely xormask with opaque mask and java-to-native code, while the program is being compiled. Oblive is successfully applied both to plain Java programs and Android apps. Showcase videos are available for the code obfuscation part https://youtu.be/Bml-BkKP3CU and for the data obfuscation part https://youtu.be/zbizYVK42ps.

Futures and promises are a high-level concurrency construct to aid the user in writing scalable and correct asynchronous programs. We introduce a simple core language based on which we can derive a rich set of future and promise features. We discuss ways to implement the core features via shared-state concurrency making either use of Software Transactional Memory, an elementary lock-based primitive, or an atomic compare-and-swap operation. The approach has been fully implemented in Haskell and Scala. For both languages, we provide empirical evidence of the effectiveness of our method. We consider program transformations in the context of futures and promises and observe potential problems in existing Scala-based libraries.

Compiling MATLAB---a dynamic, array-based language---to JavaScript is an attractive proposal: the output code can be deployed on a platform used by billions and can leverage the countless hours that have gone into making JavaScript JIT engines fast. But before that can happen, the original MATLAB code must be properly translated, making sure to bridge the semantic gaps of the two languages. An important area where MATLAB and JavaScript differ is in their handling of arrays: for example, in MATLAB, arrays are one-indexed and writing at an index beyond the end of an array extends it; in JavaScript, typed arrays are zero-indexed and writing out of bounds is a no-op. A MATLAB-to-JavaScript compiler must address these mismatches. Another salient and pervasive difference between the two languages is the assignment of arrays to variables: in MATLAB, this operation has value semantics, while in JavaScript is has reference semantics. In this paper, we present MatJuice --- a source-to-source, ahead-of-time compiler back-end for MATLAB --- and how it deals efficiently with this last issue. We present an intra-procedural data-flow analysis to track where each array variable may point to and which variables are possibly aliased. We also present the associated copy insertion transformation that uses the points-to information to insert explicit copies when necessary. The resulting JavaScript program respects the MATLAB value semantics and we show that it performs fewer run-time copies than some alternative approaches.

Dangling pointers have become an important class of software bugs that can lead to use-after-free and double-free vulnerabilities. So far, only a few approaches have been proposed to protect against dangling pointers, while most of them suffer from high overhead. In this paper, we propose a lightweight approach, named DangDone, to eliminate dangling pointers at compile time. Built upon the root cause of a dangling pointer, i.e., a pointer and its aliases are not nullified but the memory area they point to is deallocated, DangDone realizes the protection by inserting an intermediate pointer between the pointers (i.e., a pointer and its aliases) and the memory area they point to. Hence, nullifying the intermediate pointer will nullify the pointer and its aliases, which mitigates the vulnerabilities caused by dangling pointers. Experimental results have demonstrated that DangDone can protect target programs (i.e., the SPEC CPU benchmarks and the programs with known CVEs) with negligible runtime overhead (i.e., around 1% on average).

Code obfuscation is a popular approach to turn program comprehension and analysis harder, with the aim of mitigating threats related to malicious reverse engineering and code tampering. However, programming languages that compile to high level bytecode (e.g., Java) can be obfuscated only to a limited extent. In fact, high level bytecode still contains high level relevant information that an attacker might exploit. In order to enable more resilient obfuscations, part of these programs might be implemented with programming languages (e.g., C) that compile to low level machine-dependent code. In fact, machine code contains and leaks less high level information and it enables more resilient obfuscations. In this paper, we present an approach to automatically translate critical sections of high level Java bytecode to C code, so that more effective obfuscations can be resorted to. Moreover, a developer can still work with a single programming language, i.e., Java.

Program transformations and refactorings are essential elements in software development. From the early days of refactoring, tool support has emerged to provide effortless and trustworthy assistance for quality-improvement, behaviour-preserving transformations of programs. Both academia and industry have great interest in researching and developing static analysis based bug detection and trustworthy behaviour-preserving transformations. Although refactoring tools are getting better day by day, there is room for improvement both in terms of accuracy and reliability. This dissertation investigates definition and verification methods for program transformations, which can help us build more extensible, more trustworthy and widely applied transformations systems. To advance dynamic verification techniques, a novel notation for L-attribute grammars is introduced, and is given a meaning in terms of data generator functions, which can be used in various ways in property-based testing. The document presents a case study, a grammar for Erlang, and its use in testing an Erlang analysis and transformation system. To address static, formal verification of transformations, a refactoring programming language is proposed as the specification formalism for executable and semi-automatically verifiable refactoring definitions. The language is based on context-sensitive conditional term rewriting, strategy programming and refactoring schemes. Last but not least, as a special application of graph rewriting and tool-assisted program transformation, the dissertation discusses implementation of language pre-compilers in refactoring systems. With this method, a portable closure semantics was added to the Erlang programming language, enabling code migration.

Precision tuning consists of finding the least floating-point formats enabling a program to compute some results with an accuracy requirement. In mixed precision, this problem has a huge combinatory since any value may have its own format. Precision tuning has given rise to the development of several tools that aim at guarantying a desired precision on the outputs of programs doing floating-point computations, by minimizing the initial, over-estimated, precision of the inputs and intermediary results. In this article, we present an extension of our tool for numerical accuracy, Salsa, which performs precision tuning. Originally, Salsa is a program transformation tool based on static analysis and which improves the accuracy of floating-point computations. We have extended Salsa with a precision tuning static analysis. We present experimental results showing the efficiency of this new feature as well as the additional gains that we obtain by performing Salsa’s program transformation before the precision tuning analysis. We experiment our tool on a set of programs coming from various domains like embedded systems and numerical analysis.

Embedded domain-specific languages (EDSLs), inheriting a general-purpose language's features as well as look-and-feel, have traditionally been second-class or rather non-citizens in terms of host-language design. This makes sense when one regards them to be on the same level as traditional, non-EDSL library interfaces. However, this equivalence only applies to the simplest of EDSLs. In this paper we illustrate why this is detrimental when moving on to EDSLs that employ staging, i.e. program reification, by example of various issues that affect authors and users alike. We believe that if EDSLs are to be considered a reliable, language-like interface abstraction, they require exceptional attention and design scrutiny. Instead of unenforceable conventions, we advocate the acceptance of EDSLs as proper, i.e. almost first-class, citizens while retaining most advantages of pure embeddings. As a small step towards this goal, we present a pragmatic framework prototype for Java. It is based on annotations that explicate and document membership to explicit EDSL entities. In a nutshell, our framework identifies (annotated) method calls and field accesses as EDSL terms and dynamically constructs an abstract-syntax representation, which is eventually passed to a semantics-defining back end implemented by the EDSL author.

In order to achieve competitive performance, abstract machines for Prolog and related languages end up being large and intricate, and incorporate sophisticated optimizations, both at the design and at the implementation levels. At the same time, efficiency considerations make it necessary to use low-level languages in their implementation. This makes them laborious to code, optimize, and, especially, maintain and extend. Writing the abstract machine (and ancillary code) in a higher-level language can help tame this inherent complexity. We show how the semantics of most basic components of an efficient virtual machine for Prolog can be described using (a variant of) Prolog. These descriptions are then compiled to C and assembled to build a complete bytecode emulator. Thanks to the high level of the language used and its closeness to Prolog, the abstract machine description can be manipulated using standard Prolog compilation and optimization techniques with relative ease. We also show how, by applying program transformations selectively, we obtain abstract machine implementations whose performance can match and even exceed that of state-of-the-art, highly-tuned, hand-crafted emulators., 56 pages, 46 figures, 5 tables, To appear in Theory and Practice of Logic Programming (TPLP)

Pointcut fragility is a well-documented problem in Aspect-Oriented Programming; changes to the base-code can lead to join points incorrectly falling in or out of the scope of pointcuts. Deciding which pointcuts have broken due to base-code changes is a daunting venture, especially in large and complex systems. We present an automated approach that recommends pointcuts that are likely to require modification due to a particular base-code change, as well as ones that do not. Our hypothesis is that join points selected by a pointcut exhibit common structural characteristics. Patterns describing such commonality are used to recommend pointcuts that have potentially broken with a degree of confidence as the developer is typing. The approach is implemented as an extension to the popular Mylyn Eclipse IDE plug-in, which maintains focused contexts of entities relevant to the task at hand using a Degree of Interest (DOI) model. We show that it is accurate in revealing broken pointcuts by applying it to multiple versions of several open source projects and evaluating the quality of the recommendations produced against actual modifications. We found that our tool made broken pointcuts 2.14 times more interesting in the DOI model than unbroken ones, with a p-value under 0.1, indicating a significant difference in final DOI value between the two kinds of pointcuts (i.e., broken and unbroken).

Web programmers are often faced with several challenges in the development process of modern, rich internet applications. Technologies for the different tiers of the application have to be selected: a server-side language, a combination of JavaScript, HTML and CSS for the client, and a database technology. Meeting the expectations of contemporary web applications requires even more effort from the developer: many state of the art libraries must be mastered and glued together. This leads to an impedance mismatch problem between the different technologies and it is up to the programmer to align them manually. Multi-tier or tierless programming is a web programming paradigm that provides one language for the different tiers of the web application, allowing the programmer to focus on the actual program logic instead of the accidental complexity that comes from combining several technologies. While current tierless approaches therefore relieve the burden of having to combine different technologies into one application, the distribution of the code is explicitly tied into the program. Certain distribution decisions have an impact on crosscutting concerns such as information security or offline availability. Moreover, adapting the programs such that the application complies better with these concerns often leads to code tangling, rendering the program more difficult to understand and maintain. We introduce an approach to multi-tier programming where the tierless code is decoupled from the tier specification. The developer implements the web application in terms of slices and an external specification that assigns the slices to tiers. A recommender system completes the picture for those slices that do not have a fixed placement and proposes slice refinements as well. This recommender system tries to optimise the tier specification with respect to one or more crosscutting concerns. This is in contrast with current cutting edge solutions that hide distribution decisions from the programmer. In this paper we show that slices, together with a recommender system, enable the developer to experiment with different placements of slices, until the distribution of the code satisfies the programmer's needs. We present a search-based recommender system that maximises the offline availability of a web application and a concrete implementation of these concepts in the tier-splitting tool Stip.js.

Mutation testing is a program-transformation technique that injects artificial bugs to check whether the existing test suite can detect them. However, the costs of using mutation testing are usually high, hindering its use in industry. Useless mutants (equivalent and duplicated) contribute to increase costs. Previous research has focused mainly on detecting useless mutants only after they are generated and compiled. In this paper, we introduce a strategy to help developers with deriving rules to avoid the generation of useless mutants. To use our strategy, we pass as input a set of programs. For each program, we also need a passing test suite and a set of mutants. As output, our strategy yields a set of useless mutants candidates. After manually confirming that the mutants classified by our strategy as "useless" are indeed useless, we derive rules that can avoid their generation and thus decrease costs. To the best of our knowledge, we introduce 37 new rules that can avoid useless mutants right before their generation. We then implement a subset of these rules in the MUJAVA mutation testing tool. Since our rules have been derived based on artificial and small Java programs, we take our MUJAVA version embedded with our rules and execute it in industrial-scale projects. Our rules reduced the number of mutants by almost 13% on average. Our results are promising because (i) we avoid useless mutants generation; (ii) our strategy can help with identifying more rules in case we set it to use more complex Java programs; and (iii) our MUJAVA version has only a subset of the rules we derived.

Supercompilation is a program transformation technique that attempts to evaluate programs as much as possible at compile time. Supercompilation has been used for theorem proving, function inversion, and most notably optimization, especially of functional programs. However, the technique has numerous practical problems that prevent it from being applied in mainstream compilers. In this paper, we describe a framework that can be used for experimenting with supercompilation techniques. Our framework allows supercompilers to be constructed directly from an interpreter. The user specifies the interpreter using rewrite rules and the framework handles termination checking, generalization, and residualization. We demonstrate the approach by implementing a supercompiler for JavaScript.

We present a new approach for building source-to-source transformations that can run on multiple programming languages, based on a new way of representing programs called incremental parametric syntax. We implement this approach in our Cubix system, and construct incremental parametric syntaxes for C, Java, JavaScript, Lua, and Python, demonstrating three multi-language program transformations that can run on all of them. Our evaluation shows that (1) once a transformation is written, relatively little work is required to configure it for a new language (2) transformations built this way output readable code which preserve the structure of the original, according to participants in our human study, and (3) despite dealing with many languages, our transformations can still handle language corner-cases, and pass 90% of compiler test suites.

Reasoning is an important aspect for an intelligent agent to come to a rational decision. With the same importance is the ability of such an agent to adapt itself to the environment by learning new knowledge from its observations. When the agent's knowledge base is represented by a logic program, goal-directed deliberative reasoning and the adaptive ability of such an agent can be achieved by abduction and updating on logic programs, respectively. Furthermore, the tabling feature in logic programming, which affords solutions reuse rather than recomputing them, enables an agent to make an immediate decision based on past reasoning, thus avoiding repetitive deliberative reasoning. Joint tabling of logic program abduction and updating is an approach first proposed by Pereira and Saptawijaya, motivated by its application in machine ethics, enabling an agent to make moral decisions, using their system Qualm. In this paper, we provide a complete program transformation which has not been detailed on that approach. We also resolve previously unidentified issues with respect to its implementation aspects. A prototype, Qualm∗, is implemented as a proof of concept using XSB Prolog. Furthermore, an application is detailed, using Qualm”, emphasizing the importance of joint tabling of logic program abduction and updating, in the context of intelligent agents, specifically in ambient intelligence for eldercare.

The code behind dynamic webpages often includes calls to database libraries, with queries formed using a combination of static text and values computed at runtime. In this paper, we describe our work on a program analysis for extracting models of database queries that can compactly represent all queries that could be used in a specific database library call. We also describe our work on parsing partial queries, with holes representing parts of the query that are computed dynamically. Implemented in Rascal as part of the PHP AiR framework, the goal of this work is to enable empirical research on database usage in PHP scripts, to support developer tools for understanding existing queries, and to support program transformation tools to evolve existing systems and to improve the security of existing code.

Java 8 default methods, which allow interfaces to contain (instance) method implementations, are useful for the skeletal implementation software design pattern. However, it is not easy to transform existing software to exploit default methods as it requires analyzing complex type hierarchies, resolving multiple implementation inheritance issues, reconciling differences between class and interface methods, and analyzing tie-breakers (dispatch precedence) with overriding class methods to preserve type-correctness and confirm semantics preservation. In this paper, we present an efficient, fully-automated, type constraint-based refactoring approach that assists developers in taking advantage of enhanced interfaces for their legacy Java software. The approach features an extensive rule set that covers various corner-cases where default methods cannot be used. To demonstrate applicability, we implemented our approach as an Eclipse plug-in and applied it to 19 real-world Java projects, as well as submitted pull requests to popular GitHub repositories. The indication is that it is useful in migrating skeletal implementation methods to interfaces as default methods, sheds light onto the pattern's usage, and provides insight to language designers on how this new construct applies to existing software.

Many case studies have demonstrated the potential of Field-Programmable Gate Arrays (FPGAs) as accelerators for a wide range of applications. FPGAs offer massive parallelism and programmability at the bit level. This enables programmers to exploit a range of techniques that avoid many bottlenecks of classical von Neumann computing. However, development costs for FPGAs are orders of magnitude higher than classical programming. A solution would be the use of High-Level Synthesis (HLS) tools, which use C as a hardware description language. However, the C language was designed to be executed on general purpose processors, not to generate hardware. Its datatypes and operators are limited to a small number (more or less matching the hardware operators present in mainstream processors), and HLS tools inherit these limitations. To better exploit the freedom offered by hardware and FPGAs, HLS vendors have enriched the C language with integer and fixed-point types of arbitrary size. Still, the operations on these types remain limited to the basic arithmetic and logic ones. In floating point, the current situation is even worse. The operator set is limited, and the sizes are restricted to 32 and 64 bits. Besides, most recent compilers, including the HLS ones, attempt to follow established standards, in particular C11 and IEEE-754. This ensures bit-exact compatibility with software, but greatly reduces the freedom of optimization by the compiler. For instance, a floating point addition is not associative even though its real equivalent is. In the present work we attempt to give the compiler more freedom. For this, we sacrifice the strict respect of the IEEE-754 and C11 standards, but we replace it with the strict respect of a high-level accuracy specification expressed by the programmer through a pragma. The case study in this work is a program transformation that applies to floating-point additions on a loop's critical path. It decomposes them into elementary steps, resizes the corresponding subcomponents to guarantee some user-specified accuracy, and merges and reorders these components to improve performance. The result of this complex sequence of optimizations could not be obtained from an operator generator, since it involves global loop information. For this purpose, we used a compilation flow involving one or several source-to-source transformations operating on the code given to HLS tools (Figure 1).The proposed transformation already works very well on 3 of the 10 FPMarks where it improves both latency and accuracy by an order of magnitude for comparable area. For 2 more benchmarks, the latency is not improved (but not degraded either) due to current limitations of HLS tools. This defines short-term future work. The main result of this work is that HLS tools also have the potential to generate efficient designs for handling floating-point computations in a completely non-standard way. In the longer term, we believe that HLS flows can not only import application-specific operators from the FPGA literature, they can also improve them using high-level, program-level information.

Over the past few years, there is a significant shift from web to mobile devices. In addition, the success of HTML5 has negatively impacted the usage and support for Adobe Flash. This has resulted in unmaintained Flash assets and code bases. In this paper, we discuss the feasibility of a semi-automated technique to transform Flash based animations to HTML5 and JavaScript against re-writing the same animations from scratch. Writing animations from scratch in JavaScript is a time taking effort due to adherence to aesthetic details of the animation, domain knowledge and enumeration of all states. Our approach addresses these challenges by providing techniques to transform the Small Web Format (SWF) files to JavaScript. We validate our approach by conducting an experimental study to measure the efforts for a set of animations with respect to transformation from scratch, and transformation using our proposed approach. The results showed that our approach has the potential to significantly bridge the process of Flash to HTML5 migration.