Search

This poster describes the design of Mnemosyne, a distributed logger running over Named Data Networking. Mnemosyne utilizes proof of authenticity instead of proof of work. It assures immutability of logged events by interlocking all event records in a DAG mesh. By using a distributed design, Mnemosyne provides both a high logging throughput and system resiliency in face of network component failures.

In the process of the rapid development of the information society, there are still many problems in the integrity, accuracy and security of image data. Blockchain technology stands out with its characteristics of decentralization, data immutability and data openness and transparency. Therefore, in view of the above problems, this paper proposes a block chain-based image copyright confirmation and protection model. The model includes five processes: consensus node joining, generation of registration data, consensus registration data, storage of registration data, and digital watermarking. Ensure that the image information cannot be tampered with after it is stored on the blockchain, and all nodes jointly maintain the storage; At the same time, the digital watermark is added to prevent the image information from leaking out of the chain to be embezzled by criminals for personal gain.

As the underlying technology of cryptocurrency, blockchain is characterized by decentralization and immutability. It is considered as a new generation of disruptive technology. However, the underlying storage of blockchain only provides limited support for data query. This limits the utility of blockchain technology. To improve the efficiency of access to blockchain data, we design EtherH based on Ethereum, the most representative open blockchain system. EtherH is a hybrid index that can provide Single-V query and Range query on Ethereum blockchain. To make the index build more specific, EtherH supports elastic data building. A portion of the blockchain data is selected for index building. We connect the client to the Rinkeby network to obtain block data and conduct extensive experiments. Experimental results prove that EtherH performs well in both data insertion and data query.

The unique features of blockchains such as immutability, transparency, provenance, and authenticity have been used by many large-scale data management systems to deploy a wide range of distributed applications including supply chain management, healthcare, and crowdworking in permissioned settings. Unlike permissionless settings, e.g., Bitcoin, where the network is public, and anyone can participate without a specific identity, a permissioned blockchain system consists of a set of known, identified nodes that might not fully trust each other. While the characteristics of permissioned blockchains are appealing to a wide range of largescale data management systems, these systems, have to satisfy four main requirements: confidentiality, verifiability, performance, and scalability. Various approaches have been developed in industry and academia to satisfy these requirements with varying assumptions and costs. The focus of this tutorial is on presenting many of these techniques while highlighting the trade-offs among them. We demonstrate the practicality of such techniques in real-life by presenting three different applications, i.e., supply chain management, large-scale databases, and multi-platform crowdworking environments, and show how those techniques can be utilized to meet the requirements of such applications.

The immutability of blockchain is crucial to the security of many blockchain applications, while it is still desired or even legally obliged to allow for redacting the contents of blockchain for some scenarios. In this work, we revisit the conflict between the immutability and redaction of blockchain, and put forward a new fine-grained redactable blockchain with a semi-trusted regulator, who follows our protocol but has a tendency to abuse his power. To the best of our knowledge, it is the first blockchain that not only supports the supervision of blockchain content, but also allows users themselves to manage their own data. To this end, we introduce a new variant of chameleon-hash function, named stateful Chameleon Hash with Revocable Subkey, which is important for building our redactable blockchain and may be of independent interest. We also propose a black-box construction from standard chameleon-hash functions, and prove its security properties under our proposed security notions. At last, we provide a proof-of-concept implementation. The evaluation results demonstrate that our redactable blockchain is practical and can be adopted with small additional overhead compared to the immutable blockchain.

Having a transparent and convenient insurance system is desired by users, but the insurance industry currently plays differently. For example, when users ask for a fast and simple self-service, the industry may need a long and cumbersome process, and sometimes users are not sure whether they have a fair deal according to their contract. With the aim of enhancing the current bicycle insurance system in Denmark, we investigate the local market and develop BlockCycle, which is a blockchain-based bicycle insurance system. The basic idea is that insurance companies transform their insurance products into a smart contract, including the criteria of applying the product and the eligibility of compensating into program logic. When a smart contract is deployed, the immutability can ensure the deal integrity and protect both users and insurance companies from the threat of unauthorized manipulation. In addition, blockchain can provide a secure and simple way to decentralize data and services, which enables high availability and reliability. Our experimental results indicate the viability of our system.

In response to the requirements of digital copyright protection measures that ensure digital content security and support validity period management, the paper introduces a decentralized copyright protection solution that incorporates validity period control. Firstly, we propose to establish the digital copyright protection architecture based on the consortium blockchain, which ensures the authenticity of transaction information by leveraging the merits of blockchain in terms of decentralization and immutability. Secondly, a validity period control model is proposed to solve current issues in the field by applying InterPlanetary File System address mapping to digital content storage and control of mapped addresses. As the last step, content distribution and usage protocols are designed based on the above methods, which adopt asymmetric encryption methods to help eliminate the reliance on third-party key management while ensuring the security of digital contents. Experimental results prove that our solution can realize effective decentralized copyright protection with support for copyright validity period control, which is expected to have good prospects in real-world applications.

In an effort to contain the Covid-19 pandemic emergency, nations have sponsored smartphones apps tracing contacts. The ultimate aim is to alert people when a Covid-19-positive has been found and it occurs that they have been in close contact with the positive. In the context of contact tracing, transparency of data gathered is of utmost importance to show beyond doubt that the people privacy is preserved as much as possible. The proposed approach aims at making gathered data publicly available in such a way that anonymity is preserved and stored data are immutable and not owned by a single organization. For this, we equip users in a university environment with an app that reveals their presence as a proximity to a WiFi access point. While the server-side provides location ids to apps, the location history is kept within the app and checks for a possible contact are performed by the app. The server aggregates presence data related to each WiFi access point according to time-slots, and stores these periodically in a blockchain for maximum transparency and immutability. The tests on the developed prototype have shown the accuracy in determining presence data, the feasibility for apps to interact with smart contracts and to have daily presence data stored in a blockchain. The ability to exhibit official and immutable statistics on people gathering at university should be useful to give evidence of the effort to have controlled accesses and gathering avoidance.

Since coming into effect in May 2018, the EU General Data Protection Regulation (GDPR) has raised serious concerns among users of public (permissionless) blockchain systems. Such concerns are triggered by a tension between some unique characteristics of public blockchain systems and some new data subject rights introduced in the GDPR, e.g., the data immutability and the “right to erasure” (a.k.a. “the right to be forgotten”). The aim of this work is to understand how service providers and developers behind public blockchain systems have communicated about such GDPR-related challenges to their users and how the users have perceived such GDPR-related issues. To this end, for 50 public blockchain systems whose corresponding cryptocurrency had a capital market size over $150 million, we analyzed relevant communications and discussions on the following three online channels: blog and forums posts, GitHub repositories, and discussions on Twitter. Our results show that service providers and developers of the selected public blockchain systems did not play an active role in GDPR-related online discussions on Twitter. They also did not communicate with their users about GDPR on their forums and blogs frequently, where we could identify only 56 posts out of 17,821 posts for the period we studied. Our study also reveals that only an extreme minority of the studied systems (4) mentioned GDPR in their GitHub repositories. Our work adds new evidence on the lack of transparency and active communications of the public blockchain sector on the challenging GDPR compliance issue of public blockchain systems.

In this demo, we present SEBDB, a novel blockchain database that integrates immutability and transparency properties of blockchain with modeling and query ability of relational database. In summary, SEBDB has the following advantages: First, it adopts the linked structure and full replication of data among multiple participants to guarantee immutability and transparency. Second, it introduces the relational model to blockchain without introducing extra overhead, based on which relational queries are supported. SEBDB supports SQL-like language as the general interface to support convenient application development, in which intrinsic operations are re-defined and re-implemented to suit for blockchain platform. Third, it supports rich verifiable queries based on the proposed authenticated index, thin clients can participate in the system regardless of limitations of storage, network, and computing resources. We demonstrate the usability and scalability of SEBDB using a donation system.

Blockchain is viewed as one of the most promising and disruptive inventions and is considered to have the potential to significantly change current auditing profession and reshape the business ecosystem. With the advancement of blockchain, it has been concerned in some studies that auditing could be significantly impacted and eventually replaced. Meanwhile, another viewpoint argues that blockchain technology would push the existing auditing industry to a new direction rather than eliminating the need for auditing in the immediate future. This discussion can hardly be settled without evaluation, however, studies exploring how blockchain technology can be employed in auditing practice or how continuous auditing can be conducted using blockchain technology are limited. This paper analyses the impact of blockchain features on existing audit processes and discusses the possibility of applying blockchain characteristics including immutability, distributed ledger, real-time settlement to the auditing domain. Based on the systematic analysis, this study proposes a conceptual model for blockchain-based auditing information system, which provides solutions to employ blockchain technology in auditing profession, significantly improving the efficiency and effectiveness of auditing and promoting the transformation of the auditing paradigm to real-time, continuous and intelligent auditing.

Blockchain has been a part of people's interest in the development of various areas such as digital currencies (e.g., Bitcoin), securities, healthcare, record-keeping and much more. Some of the key features of blockchain technology are immutability, decentralization, distributed ledger, consensus, and smart contract. In this paper, we explore how blockchain technology could possibly be utilized for the academic credential attestation in the education domain. This paper aims to re-engineer the academic credential attestation process to reduce both time and resource consumption and human involvement. It also aims to design a unique way for academic data collection to prevent fraud academic credentials. A blockchain-based system for academic credential attestation has been implemented.

Functional programming languages contain a number of runtime and language features, such as garbage collection, indirect memory accesses, linked data structures and immutability, that interact with a processor’s memory system. These conspire to cause a variety of unintuitive memory performance effects. For example, it is slower to traverse through linked lists and arrays of data that have been sorted than to traverse the same data accessed in the order it was allocated. We seek to understand these issues and mitigate them in a manner consistent with functional languages, taking advantage of the features themselves where possible. For example, immutability and garbage collection force linked lists to be allocated roughly sequentially in memory, even when the data pointed to within each node is not. We add language primitives for software-prefetching to the OCaml language to exploit this, and observe significant performance improvements a variety of micro- and macro-benchmarks, resulting in speedups of up to 2× on the out-of-order superscalar Intel Haswell and Xeon Phi Knights Landing systems, and up to 3× on the in-order Arm Cortex-A53.

Online shopping interoperability is focused a long-time ago in data exchange between the shop and the logistics companies. For the payment system, it also communicates well with the banking system. However, revocation transaction issue is still difficult to be handled while enabling interoperability because it involves fairness of related parties and difficulty in maintaining the transaction process till the end. In this paper, we present how blockchain technology might help solving the problem through four aspects: (1) digital access rules, (2) data immutability, (3) package tracking and update, and (4) easy payment management. We then propose payment distribution formulas to address the revocation issue.

Aliasing is an essential concept in programming languages, used to represent self-referential structures and share data between components. Unfortunately, it is also a common source of software bugs that are often hard to find and fix. In response, a plethora of methods have been proposed to tame aliasing. They usually rely on uniqueness and/or immutability to establish strong safety guarantees, but are often too restrictive to write common idioms, as they generally enforce a single-writer policy. This paper suggests to relax this constraint by focusing on the specific parts of an object representation for which aliasing should be controlled, otherwise allowing unrestricted mutations of its fields.

Performance agencies broke contracts between performance management firms and customers and receive commission. However, they respond passively to contracts using macro. In order to solve the problems arising for contracts using macro, this study aims at designing and implementing a direct contract system between performance management firms and customers, using peer-to-peer method of blockchain, without brokers.

With the rapid development of Internet, security and privacy of the Domain Name System (DNS) are becoming increasingly important. Thanks to its decentralized structure and immutability, blockchain technology has the potential to address relevant security and privacy challenges in the DNS. In this paper, we survey the blockchain-based DNS for different architectures. We envision our study to motivate more studies on the DNS based on the blockchain.

Result caching is crucial to the performance of data processing systems, but two trends complicate its use. First, immutable datasets make it difficult to efficiently employ powerful result caching techniques like predicate analysis, since predicate analysis typically requires optimized query plans but generating those plans can be costly with data immutability. Second, increased support for user-defined functions (UDFs), which are treated as black boxes by query engines, hinders aggressive result caching. This paper overcomes these problems by introducing 1) a judicious adaptation of predicate analysis on analyzed query plans that avoids unnecessary query optimization, and 2) a UDF translator that transparently compiles UDFs from general purpose languages into native equivalents. We then present Acorn, a concrete implementation of these techniques in Spark SQL that provides speedups of up to 5x across multiple benchmark and real Spark graph processing workloads.

Federated learning (FL) is promising in supporting collaborative learning applications that involve large datasets, massively distributed data owners and unreliable network connectivity. To protect data privacy, existing FL approaches adopt (k,n)-threshold secret sharing schemes, based on the semi-honest assumption for clients, to enable secure multiparty computation in local model update exchange which deals with random client dropouts at the cost of increasing data size. These approaches adopt the semi-honest assumption for clients, therefore they are vulnerable to malicious clients. In this work, we propose a blockchain-based privacy-preserving federated learning (BC-based PPFL) framework, which leverages the immutability and decentralized trust properties of blockchain to provide provenance of model updates. Our proof-of-concept implementation of BC-based PPFL demonstrates it is practical for secure aggregation of local model updates in the federated setting.

Despite the promising benefits such as expanded signature databases and alert data from multiple sites, trust management and consensus building remain as challenges for a Collaborative Intrusion Detection System (CIDS) to work effectively. The blockchain technology with built-in immutability and consensus building capability provides a viable solution to the issues of CIDS. In this paper, we introduce an architecture for a blockchain-enabled signature-based collaborative IDS.

Internet of Things(IoT) is playing a vital role in making the digital world smarter with widely adopted applications. One of the important application of such a system is Smart Power Grid. A critical system like Smart Power Grid requires stringent security measures like immutability of the data sensed by IoT based sensors, verifiability of records etc. It is also important that the system works in a decentralised manner as there are multiple sources of power in a Grid which are from different administrative domain. This paper represents a system which will help to address concerns about security, privacy, Identity along with immutability and verifiability of records. The proposed system allows exchange and collection of data in a decentralized, peer-to-peer, trustless network of devices using BlockChain.

Functional (aka immutable) data structures are used extensively in data management systems. From distributed systems to data persistence, immutability makes complex programs significantly easier to reason about and implement. However, immutability also makes many runtime optimizations like tree rebalancing, or adaptive organizations, unreasonably expensive. In this paper, we propose Fluid data structures, an approach to data structure design that allows limited physical changes that preserve logical equivalence. As we will show, this approach retains many of the desirable properties of functional data structures, while also allowing runtime adaptation. To illustrate Fluid data structures, we work through the design of a lazy-loading map that we call a Fluid Cog. A Fluid Cog is a lock-free data structure that incrementally organizes itself in the background by applying equivalence-preserving structural transformations. Our experimental analysis shows that the resulting map structure is flexible enough to adapt to a variety of performance goals, while remaining competitive with existing structures like the C++ standard template library map.

Governments across the world are testing different uses of the blockchain for the delivery of their public services. Blockchain hashing-or the insertion of data in the blockchain (anchoring)-is one of the potential applications of the blockchain in this space. With this method, users can apply special scripts to add their data to blockchain transactions, ensuring both immutability and publicity. Blockchain hashing also secures the integrity of the original data stored on central governmental databases. The objective of this paper is to analyse the use of data hashing (anchoring) on the blockchain for public state-owned registries. This paper starts by analysing possible scenarios of hashing on the blockchain and assesses in which cases it may work and in which it is less likely to add value to a public administration. Second, the paper also compares this method with traditional digital signatures using PKI (Public Key Infrastructure) and discusses standardisation in each domain. Third, it also addresses issues related with concepts such as "distributed ledger technology" and "permissioned blockchains." Finally, it raises the question of whether blockchain hashing is an effective solution for electronic governance, and concludes that its value is controversial, even if it is improved by PKI and other security measures. In this regard, we claim that governments need to identify pain points in governance in the first place, and then consider the trade-offs of the blockchain as a potential solution versus other alternatives.

Static analyses which compute conceptually independent information, e.g., class immutability or method purity are typically developed as standalone, closed analyses. Complementary information that could improve the analyses is either ignored by making a sound over-approximation or it is also computed by the analyses, but at a rudimentary level. For example, an immutability analysis requires field mutability information, alias/escape information, and information about the concurrent behavior of methods to correctly classify classes like java.lang.String or java.util.BigDecimal. As a result, without properly supporting the integration of independently developed, mutually benefiting analysis, many analyses will not correctly classify relevant entities.We propose to use explicitly reified lattices that encode the information about a source code element's properties (e.g., a method's purity or a class' immutability) as the sole interface between mutually dependent analyses. This enables the composition of multiple analyses. Our case study shows that using such an approach enables highly scalable, lightweight implementations of modularized static analyses.

With the emergence of Bitcoin, businesses are focusing on leveraging Bitcoin's blockchain technology to non-cryptocurrency based applications to improve efficiency of the operations. These business applications operate in environments where participants have verified identities; these are called permissioned environments. Blockchain is an immutable and append only distributed ledger that can be utilized for record keeping applications. We observe that when blockchain technology is adapted from permissionless environments to permissioned environments the immutability of blockchain becomes questionable as the end-users may not monitor or store a copy of the blockchain. We propose the use of Keyless Signatures' Infrastructure as an additional mechanism to ensure irreversible and irrefutable proof of block confirmations which acts as a global proof thus preserving long term immutability of blockchain in permissioned environments.

Immutability is a valuable feature for programmers in object-oriented languages: making objects immutable often simplifies reasoning about the correctness of code, particularly when concurrency is present. Java allows programmers to express and enforce immutability by declaring all fields of an object "final", but this comes at the cost of decreased expressiveness and intuitiveness of initialization. In this work, we propose a minimalistic type-based mechanism that both enforces immutability and relaxes these constraints on initialization. Furthermore, we propose and formalize two different type systems based on this mechanism that form a meaningful trade-off with respect to complexity, expressiveness, and strength of static guarantees. System One is simple, more expressive, and provides object-level immutability; System Two has more complicated annotation, is less expressive, and ensures that immutable objects are fully initialized in addition to enforcing immutability.

Collection data structures in standard libraries of programming languages are designed to excel for the average case by carefully balancing memory footprint and runtime performance. These implicit design decisions and hard-coded trade-offs do constrain users from using an optimal variant for a given problem. Although a wide range of specialized collections is available for the Java Virtual Machine (JVM), they introduce yet another dependency and complicate user adoption by requiring specific Application Program Interfaces (APIs) incompatible with the standard library. A product line for collection data structures would relieve library designers from optimizing for the general case. Furthermore, a product line allows evolving the potentially large code base of a collection family efficiently. The challenge is to find a small core framework for collection data structures which covers all variations without exhaustively listing them, while supporting good performance at the same time. We claim that the concept of Array Mapped Tries (AMTs) embodies a high degree of commonality in the sub-domain of immutable collection data structures. AMTs are flexible enough to cover most of the variability, while minimizing code bloat in the generator and the generated code. We implemented a Data Structure Code Generator (DSCG) that emits immutable collections based on an AMT skeleton foundation. The generated data structures outperform competitive hand-optimized implementations, and the generator still allows for customization towards specific workloads.

Reference immutability guarantees that a reference is not used to modify the referenced object. It is well-understood and there are several scalable inference systems. Object immutability, a stronger immutability guarantee, guarantees that an object is not modified. Unfortunately, object immutability is not as well-understood; specifically, we are unaware of an inference system that infers object immutability across large Java programs and libraries.It is tempting to use reference immutability to reason about object immutability. However, representation exposure and object initialization pose significant challenges.In this paper we present a novel type system and a corresponding inference analysis. We leverage reference immutability to infer object immutability overcoming the challenges due to representation exposure and object initialization.We have implemented our object immutability system for Java. Evaluation on the standard Dacapo benchmarks demonstrates precision and scalability. Nearly 40% of all static objects are inferred immutable. Analysis completes in under 2 minutes on all benchmarks.

Programming languages can restrict state change by preventing it entirely (immutability) or by restricting which clients may modify state (read-only restrictions). The benefits of immutability and read-only restrictions in software structures have been long-argued by practicing software engineers, researchers, and programming language designers. However, there are many proposals for language mechanisms for restricting state change, with a remarkable diversity of techniques and goals, and there is little empirical data regarding what practicing software engineers want in their tools and what would benefit them. We systematized the large collection of techniques used by programming languages to help programmers prevent undesired changes in state. We interviewed expert software engineers to discover their expectations and requirements, and found that important requirements, such as expressing immutability constraints, were not reflected in features available in the languages participants used. The interview results informed our design of a new language extension for specifying immutability in Java. Through an iterative, participatory design process, we created a tool that reflects requirements from both our interviews and the research literature.

Many programming languages provide features that express restrictions on which data structures can be changed. For example, C++ includes const and Java includes final. Languages that are in widespread use typically provide non-transitive immutability: when a reference is specified to be immutable or read-only, the object referenced can still reference mutable structures. However, some languages, particularly research languages, provide transitive immutability, in which immutable objects can only reference other immutable objects (with some exceptions). We are designing a lab study of programmers to elucidate the differences in programmer effectiveness between these two approaches.

Combining the actor-model with shared memory for performance is efficient but can introduce data-races. Existing approaches to static data-race freedom are based on uniqueness and immutability, but lack flexibility and high performance implementations. Our approach, based on deny properties, allows reading, writing and traversing unique references, introduces a new form of write uniqueness, and guarantees atomic behaviours.

The questions of protection of information systems against threats of functional failures are considered. The concept of active protection technology realizing the functional restructuring of the system is suggested. The conceptual apparatus of functional redundancy are developed. The principles of operation of the immutability of purpose and principle of operation of the reduction target are defined. The classification of methods to ensure functional stability is submitted.

HIPimm, an extension of the HIP/SLEEK automatic verification system, offers immutability guarantees on top of ensuring functional correctness for heap-manipulating programs. The extra capability of HIPimm, as compared to its precursor, is the ability to reason about immutability guarantees in a granular manner.For this purpose, we enhance the specification language with immutability annotations which provide the means to assert whether the annotated heap can be mutated or whether is inaccessible. As part of user defined predicates, these annotations are integrated at the data field level offering granular immutability guarantees. An immediate result of this new functionality is a finer level of precision in the verification process of programs involving heap data structures. That is, we enable the verification of program properties such as preservation of data structures shapes and/or values, flexible aliases, and information leakage prevention.

Information flow type systems, such as EnerJ (a type system for energy efficiency), and integrity and confidentiality, are unsound if subtyping for references is allowed because of the presence of mutable references. The standard approach is to disallow subtyping for references, or in other words, replace subtyping constraints with equality constraints. Unfortunately, this often leads to imprecision, causing the type system to reject valid programs. We observe that subtyping is safe when the left-hand-side of the assignment is immutable. Therefore, we compose information flow systems with reference immutability, which allows for limited subtyping for references. We infer types with the standard approach (i.e., no subtyping for references), and with the composition approach on 13 Java web applications. The composition approach achieves at least 20% precision improvement over the standard approach.

Pluggable types can help find bugs such as null-pointer dereference or unwanted mutation (or they can prove the absence of such bugs). Unfortunately, pluggable types require annotations, which imposes a burden on programmers.We propose a framework for specifying, inferring and checking of context-sensitive pluggable types. Programmers can use the framework to plug existing context-sensitive type systems (e.g., Immutability, Ownership) as well as to build new systems.

Reference immutability ensures that a reference is not used to modify the referenced object, and enables the safe sharing of object structures. A pure method does not cause side-effects on the objects that existed in the pre-state of the method execution. Checking and inference of reference immutability and method purity enables a variety of program analyses and optimizations. We present ReIm, a type system for reference immutability, and ReImInfer, a corresponding type inference analysis. The type system is concise and context-sensitive. The type inference analysis is precise and scalable, and requires no manual annotations. In addition, we present a novel application of the reference immutability type system: method purity inference. To support our theoretical results, we implemented the type system and the type inference analysis for Java. We include a type checker to verify the correctness of the inference result. Empirical results on Java applications and libraries of up to 348kLOC show that our approach achieves both scalability and precision.

A key challenge for concurrent programming is that side-effects (memory operations) in one thread can affect the behavior of another thread. In this paper, we present a type system to restrict the updates to memory to prevent these unintended side-effects. We provide a novel combination of immutable and unique (isolated) types that ensures safe parallelism (race freedom and deterministic execution). The type system includes support for polymorphism over type qualifiers, and can easily create cycles of immutable objects. Key to the system's flexibility is the ability to recover immutable or externally unique references after violating uniqueness without any explicit alias tracking. Our type system models a prototype extension to C# that is in active use by a Microsoft team. We describe their experiences building large systems with this extension. We prove the soundness of the type system by an embedding into a program logic.

We develop a mechanized proof of Featherweight Java with Assignment and Immutability in the Coq proof assistant. This is a step towards more machine-checked proofs of a non-trivial type system. We used object immutability close to that of IGJ [9] . We describe the challenges of the mech- anisation and the encoding we used inside of Coq.

In the current work, we investigate the benefits of immutability guarantees for allowing more flexible handling of aliasing, as well as more precise and concise specifications. Our approach supports finer levels of control that can mark data structures as being immutable through the use of immutability annotations. By using such annotations to encode immutability guarantees, we expect to obtain better specifications that can more accurately describe the intentions, as well as prohibitions, of the method. Ultimately, our goal is improving the precision of the verification process, as well as making the specifications more readable, more precise and as an enforceable program documentation. We have designed and implemented a new entailment procedure to formally and automatically reason about immutability enhanced specifications. We have also formalised the soundness for our new procedure through an operational semantics with mutability assertions on the heap. Lastly, we have carried out a set of experiments to both validate and affirm the utility of our current proposal on immutability enhanced specification mechanism.

It is common for object-oriented programs to have both mutable and immutable classes. Immutable classes simplify programing because the programmer does not have to reason about side-effects. Sometimes programmers write immutable classes from scratch, other times they transform mutable into immutable classes. To transform a mutable class, programmers must find all methods that mutate its transitive state and all objects that can enter or escape the state of the class. The analyses are non-trivial and the rewriting is tedious. Fortunately, this can be automated. We present an algorithm and a tool, Immutator, that enables the programmer to safely transform a mutable class into an immutable class. Two case studies and one controlled experiment show that Immutator is useful. It (i) reduces the burden of making classes immutable, (ii) is fast enough to be used interactively, and (iii) is much safer than manual transformations.

The Java language lacks the important notions of ownership (an object owns its representation to prevent unwanted aliasing) and immutability (the division into mutable, immutable, and readonly data and references). Programmers are prone to design errors, such as representation exposure or violation of immutability contracts. This paper presents Ownership Immutability Generic Java (OIGJ), a backward-compatible purely-static language extension supporting ownership and immutability. We formally defined a core calculus for OIGJ, based on Featherweight Java, and proved it sound. We also implemented OIGJ and performed case studies on 33,000 lines of code. Creation of immutable cyclic structures requires a "cooking phase" in which the structure is mutated but the outside world cannot observe this mutation. OIGJ uses ownership information to facilitate creation of immutable cyclic structures, by safely prolonging the cooking phase even after the constructor finishes. OIGJ is easy for a programmer to use, and it is easy to implement (flow-insensitive, adding only 14 rules to those of Java). Yet, OIGJ is more expressive than previous ownership languages, in the sense that it can type-check more good code. OIGJ can express the factory and visitor patterns, and OIGJ can type-check Sun's java.util collections (except for the clone method) without refactoring and with only a small number of annotations. Previous work required major refactoring of existing code in order to fit its ownership restrictions. Forcing refactoring of well-designed code is undesirable because it costs programmer effort, degrades the design, and hinders adoption in the mainstream community.

OO languages typically provide one form of object equality, known as reference equality, where two objects are equal only if they are the same object; two objects which are structurally identical are not considered equal. Thus, programmers who require a more refined notion of equality must define their own operator. Programmer-implemented equality operators tend to rely on informal notions of partial and temporal object immutability which are prone to error. This is a particular problem for objects used in collections which depend on equality. This paper discusses Affinity: an untyped, object-oriented language with a powerful equality operator based on EGAL [2] and support for object-keying and immutability. Affinity is designed to provide coherent and elegant support for object equality, reducing programmer burden and error potential.

Immutability information is useful in many software engineering tasks, such as modeling, verification, optimization, and refactoring. Furthermore, undesired mutation or side-effect are hard to detect and debug. This paper describes a javac plug-in that enables programmers to write immutability annotations in a Java program to detect and prevent bugs. The IGJ annotations are rich and flexible; the tools are scalable; case studies show they are effective and easy to use; and the annotated program remains compilable with a standard compiler.

Accidental mutation is a major source of difficult-to-detect errors in object-oriented programs. We have built tools that detect and prevent such errors. The tools include a javac plug-in that enforces the Javari type system, and a type inference tool. The system is fully compatible with existing Java programs.

A compiler-checked immutability guarantee provides useful documentation, facilitates reasoning, and enables optimizations. This paper presents Immutability Generic Java (IGJ), a novel language extension that expresses immutability without changing Java's syntax by building upon Java's generics and annotation mechanisms. In IGJ, each class has one additional type parameter that is Immutable, Mutable, or ReadOnly. IGJ guarantees both reference immutability (only mutable references can mutate an object) and object immutability (an immutable reference points to an immutable object). IGJ is the first proposal for enforcing object immutability within Java's syntax and type system, and its reference immutability is more expressive than previous work. IGJ also permits covariant changes of type parameters in a type-safe manner, e.g., a readonly list of integers is a subtype of a readonly list of numbers. IGJ extends Java's type system with a few simple rules. We formalize this type system and prove it sound. Our IGJ compiler works by type-erasure and generates byte-code that can be executed on any JVM without runtime penalty.

This paper describes a type system that is capable of expressing and enforcing immutability constraints. The specific constraint expressed is that the abstract state of the object to which an immutable reference refers cannot be modified using that reference. The abstract state is (part of) the transitively reachable state: that is, the state of the object and all state reachable from it by following references. The type system permits explicitly excluding fields from the abstract state of an object. For a statically type-safe language, the type system guarantees reference immutability. If the language is extended with immutability downcasts, then run-time checks enforce the reference immutability constraints.This research builds upon previous research in language support for reference immutability. Improvements that are new in this paper include distinguishing the notions of assignability and mutability; integration with Java 5's generic types and with multi-dimensional arrays; a mutability polymorphism approach to avoiding code duplication; type-safe support for reflection and serialization; and formal type rules and type soundness proof for a core calculus. Furthermore, it retains the valuable features of the previous dialect, including usability by humans (as evidenced by experience with 160,000 lines of Javari code) and interoperability with Java and existing JVMs.

This paper describes a type system that is capable of expressing and enforcing immutability constraints. The specific constraint expressed is that the abstract state of the object to which an immutable reference refers cannot be modified using that reference. The abstract state is (part of) the transitively reachable state: that is, the state of the object and all state reachable from it by following references. The type system permits explicitly excluding fields or objects from the abstract state of an object. For a statically type-safe language, the type system guarantees reference immutability. If the language is extended with immutability downcasts, then run-time checks enforce the reference immutability constraints. In order to better understand the usability and efficacy of the type system, we have implemented an extension to Java, called Javari, that includes all the features of our type system. Javari is interoperable with Java and existing JVMs. It can be viewed as a proposal for the semantics of the Java const keyword, though Javari's syntax uses readonly instead. This paper describes the design and implementation of Javari, including the type-checking rules for the language. This paper also discusses experience with 160,000 lines of Javari code. Javari was easy to use and provided a number of benefits, including detecting errors in well-tested code.

A location is said to be immutable if its value and the values of selected locations reachable from it are guaranteed to remain unchanged during a specified time interval. We introduce a framework for immutability specification, and discuss its application to code optimization. Compared with a final declaration, an immutability assertion in our framework can express a richer set of immutability properties along three dimensions—lifetime, reachability and context. We present a framework for processing and verifying immutability annotations in Java, as well as extending optimizations so as to exploit immutability information. Preliminary experimental results show that a significant number (61%) of read accesses could potentially be classified as immutable in our framework. Further, use of immutability information yields substantial reductions (33–99%) in the number of dynamic read accesses, and also measurable speedups in the range of 5–10% for certain benchmark programs. Copyright © 2005 John Wiley & Sons, Ltd.

The greatest challenge you, the writer, will face when creating a manual is to design one that is used, a manual that the user loves, a manual with dog-eared pages, yellow highlighter and handwritten notes. Don't you wish your manuals would look as used as the yellow pages do after just one year's use?Yet, writers are also holders of manuals, many of which we do not use. Is there an out-of-date manual tucked into the bottom shelf of your bookcase, dusty with disuse? Do you know if it is even relevant anymore?The business community is littered with beautiful manuals, color-coded headings, amazing graphics—but they're useless, because the information is out of date. Sometimes it seems as though the writer had been trying to create a document like the U.S. Constitution, which has remained virtually unchanged in 200 years. Now there is a document that has stood the test of time. But it required 55 men almost 17 weeks to bring a document of 4,000 words to publication.Should we be striving for such immutability? Are we expecting to create manuals that will stand the test of time? Is this a realistic or even a practical goal? Or should we design our documents from the beginning for change?A manual is not a dead object, created once, then left on the shelf like a vase. It is a living, evolving document, that must be nurtured with new information, with new approaches. Without this evolution, it will die.