Vasiliki Diamantopoulou
email: v.diamantopoulou@brighton.ac.uk

Christos Kalloniatis

Stefanos Gritzalis

Haralambos Mouratidis
email: h.mouratidis@brighton.ac.uk

Supporting Privacy by Design using Privacy Process Patterns

Keywords: Privacy Process Patterns, Requirements Engineering, Information Security Modelling

Advances in Information and Communication Technology (ICT) have had significant impact on every-day life and have allowed us to share, store and manipulate information easily and at any time. On the other hand, such situation also raises important privacy concerns.

To deal with such concerns, the literature has identified the need to introduce a Privacy by Design (PbD) approach to support the elicitation and analysis of privacy requirements and their implementation through appropriate Privacy Enhancing Technologies. However, and despite all the work presented in the literature, there is still a gap between privacy design and implementation. This paper presents a set of Privacy Process Patterns that can be used to bridge that gap. To demonstrate the practical application of such patterns, we instantiate them in JavaScript Object Notation (JSON), we use them in conjunction with the Privacy Safeguard (PriS) methodology and we apply them to a real case study.

Introduction

Information Privacy is considered as an important challenge for Information and Communication Technology (ICT). With more and more sensitive and confidential information stored, shared and manipulated at digital level [START_REF] Duncan | Enhancing access to microdata while protecting confidentiality: Prospects for the future[END_REF], both individuals and organisations expect appropriate measures to ensure privacy of such information. However, this is not easy, as privacy is a multifaceted concept with various impact and ways of achievement which depends, amongst other things, on the environments in which it is required to be achieved.

Although the paradigm of Privacy by Design (PbD) has been proposed as a feasible solution to such situation, there are still major challenges that require further research and development. In particular, a challenging task in the context of PbD is moving from a design (where the privacy requirements of an information system have been elicited) to an implementation that fulfils those requirements. This is problematic for two main reasons. On one hand, there is little expertise on how best to align privacy requirements (from the design stage) to Privacy Enhancing Technologies (PETs) [START_REF] Hes | Privacy Enhancing Technologies: the path to anonymity[END_REF] at implementation stage. On the other hand, software engineers, who need to deal with both the design and the implementation stages, lack detailed knowledge of PETs to ensure correct implementation. This paper contributes towards these two challenges by proposing a set of Privacy Process Patterns to enhance detailed knowledge of PETs and a clear alignment between privacy properties (requirements) and PETs. Moreover, we are demonstrating how these patterns can be used as part of a privacy-aware methodology to bridge the gap between design and implementation. To improve the usability of such patterns, we instantiate them with JavaScript Object Notation (JSON), using a template that could be adapted by any programming language. Moreover, we present our patterns in the context of an existing privacy-aware methodology called PriS [START_REF] Kalloniatis | Addressing privacy requirements in system design: the PriS method[END_REF] and we apply our work to a real case study to illustrate practical applicability of the work.

The paper is structured as follows. Section 2 discusses the related work, while Section 3 presents the Privacy Process Patterns. Section 4 describes their implementation and Section 5 illustrates their application to a case study. Finally, Section 6 concludes the paper.

Related Work

Patterns have been adopted into software engineering as they encounter each problem in a systematic and structured way. Privacy patters, specifically, have been used as a way to model privacy issues. In [START_REF] Romanosky | Privacy patterns for online interactions[END_REF] privacy patterns are used for web-based activity and especially for conveying privacy policies to end-users during online interactions. Traditional design patterns are described in [START_REF] Chung | Development and evaluation of emerging design patterns for ubiquitous computing[END_REF], identifying 45 patterns for the design in ubiquitous computing environments, 15 of which focused on privacy. The authors in [START_REF] Hafiz | A pattern language for developing privacy enhancing technologies[END_REF] propose a pattern language which contains 12 patterns for developing anonymity solutions for various domains, including anonymous messaging, anonymous voting and location anonymity. This work moves on the right direction regarding the modelling of privacy requirements but it fails to combine privacy elicitation concepts for capturing privacy requirements. In [START_REF] Schümmer | The public privacy-patterns for filtering personal information in collaborative systems[END_REF], six patterns that focus on how to establish boundaries for interaction are presented, focusing on the filtering of personal information in collaborative systems. Finally, the author in [START_REF] Schumacher | Security Patterns and Security Standards[END_REF] presented two privacy patterns, applying this approach to security issues by proposing a set of security patterns to be applied during the software development process.

Privacy Process Patterns

Privacy Process Patterns are patterns being applied on privacy related processes in order to specify the way that the respective privacy issues will be realised through a specific number of steps, including activities and flows connecting them. They assist developers to understand, in a better and more specific way, how to implement the various privacy properties. The use of Privacy Process Patterns is considered as a more robust way for bringing the gap between the design and the implementation phase of a system or module of it.

The proposed pattern structure follows the so-called Alexandrian format [START_REF] Alexander | A pattern language: towns, buildings, construction[END_REF] which is already accepted and used for the definition of security patterns [START_REF] Mouratidis | Security patterns meet agent oriented software engineering: a complementary solution for developing secure information systems[END_REF]. This format is efficient enough for the description of the Privacy Process Patterns, matching the fields of each pattern when this is expressed with JSON. Through definition field, we give a comprehensive definition of the property. The fields problems and forces present the goals that need to be fulfilled and the forces that need to be considered when choosing to use this pattern, respectively. The fields benefits and liabilities present the advantages and the disadvantages that are identified in each privacy property. The field implementation techniques covers all the possible techniques that satisfy the respective property. From the range of the proposed implementation techniques, the developers can choose the most appropriate technology based on the privacy process patterns applied on every privacy-related process. Finally, the field of related patterns indicates which patterns have similar characteristics with the examined one, which patterns are closely related in terms of functionality and with which other patterns it can be utilised.

This work describes the five basic privacy properties [START_REF] Fischer-Hübner | IT-security and privacy: design and use of privacy-enhancing security mechanisms[END_REF], [START_REF] Cannon | Privacy: What developers and IT professionals should know[END_REF], [START_REF] Pfitzmann | A terminology for talking about privacy by data minimization: Anonymity, unlinkability, undetectability, unobservability[END_REF], [START_REF]Information technology -Security techniques -Privacy framework[END_REF] namely anonymity, pseudonymity, unlinkability, undetectability and unobservability. Our intention is to define a general template for privacy properties that can be used to describe other properties additionally to the five we enlisted above. This is a preliminary work aiming to identify all possible privacy concepts that need to be addressed when designing privacy-aware systems and provide a structured description in order for the developers to take advantage of and manage to handle privacy in a robust way, linking the gap between design and implementation phases. The impact of the selection of respective privacy concepts and the complexity of their applicability is a very interesting topic, but it is not the main focus of this paper. This template comprises a guide for the developers who can understand in a better and more structured way how to implement each privacy concept.

Anonymity

-Definition: Anonymity is a characteristic of information that does not permit a personally identifiable information principal to be identified directly or indirectly. During anonymization, identity information is either erased or substituted -Problem: The user of a service cannot be identified -Forces: Large number of users in the same network is required -Benefits: i) Supports users in accessing services without disclosing their identity, ii) Users are more freely expressed, since freedom from user profiling is achieved (behaviour of users or other privacy-infringing practices), iii) Freedom from location tracking, iv) Minimal user involvement (they do not have to modify their normal activities for anonymity services) -Liabilities: i) Maintain users' accountability while anonymous, Performance (latency, loss of functionality, bandwidth, etc.), ii) Usability of information (too much data obfuscation can undermine the usefulness of data), iii) Abuse of privacy (malicious users), iv) User count (large anonymity set), v) User friendliness (if the users have to adapt a lot to achieve anonymity, they may start judging where they should have anonymity), vi) Law enforcement (the anonymity might have to be liftable to investigate on crime suspects) -Implementation techniques:

• Anonymizer products, services and architectures: Browsing pseudonyms [START_REF] Gabber | How to make personalized web browsing simple, secure, and anonymous[END_REF], Virtual Email Addresses, Trusted third parties, Crowds [START_REF] Reiter | Crowds: Anonymity for web transactions[END_REF], Onion routing [START_REF] Goldschlag | Onion routing[END_REF], DC-nets [START_REF] Chaum | The dining cryptographers problem: Unconditional sender and recipient untraceability[END_REF], Mix-nets (Mix Zone) [START_REF] Chaum | Untraceable electronic mail, return addresses, and digital pseudonyms[END_REF], Hordes [START_REF] Shields | A protocol for anonymous communication over the Internet[END_REF], GAP [START_REF] Bennett | GAP-practical anonymous networking[END_REF], Tor [START_REF] Dingledine | Tor: The second-generation onion router[END_REF], Aggregation Gateway [START_REF] Akers | Service Aggregation Gateway[END_REF], Dynamic Location Granularity • Track and evident erasers: Spyware detection and removal, Hard disk data eraser, User data confinement pattern, Use of dummies -Related patterns: Pseudonymity, unlinkability

Pseudonymity

-Definition: Pseudonymity is the utilisation of an alias instead of personally identifiable information -Problem: Ensuring that an entity cannot be linked with a real identity during online interactions -Forces: Use authenticated services without disclosing identifiable information -Benefits: i) Supports users in accessing services without disclosing their real identity, ii) Permits the accumulation of reputational capital, iii) The user is still accountable for its actions, iv) A user may have a number of pseudonyms, v) Fills the gap between accountability and anonymity, vi) Hides the identity of the participants, vii) Prevents unforeseen ramifications of the use of online services -Liabilities: i) Maintains users' accountability while pseudonymous, ii) Abuse of privacy (malicious users) iii) Forgery/impersonation, iv) Law enforcement (the anonymity might have to be liftable to investigate on crime suspects), v) Extensive usage of the same pseudonym can weaken it -Implementation techniques:

• Administrative tools: Identity management, Biometrics [START_REF]Handbook of biometrics[END_REF], Smart cards [START_REF] Weis | Security and privacy aspects of low-cost radio frequency identification systems[END_REF], Permission management • Pseudonymizer tools: CRM personalisation [START_REF] Mulvenna | Personalization on the Net using Web mining: introduction[END_REF], Application data management, Obligation management, Mixmaster -Related patterns: Anonymity, authentication

Unlinkability

-Definition: Unlinkability is the use of a resource or a service by a user without a third party being able to link the user with the service -Problem: i) Users' identifiable information is not protected, ii) The strength of unlinkability is depended on the number of nodes belonging to the unlinkability set -Forces: Enforce users' privacy regarding the linkability with the service used -Benefits: i) Protect users' privacy when using a resource or service by not allowing malicious third parties to monitor which services are used by the user, ii) The intentional severing of the relationships (links) between two or more data events and their sources, ensures that a user may make multiple uses of resources or services without others being able to link the uses together, iii) Requires that users and/or subjects are unable to determine whether the same user caused certain specific operations in the system, iv) Minimise risks to the misuse of the privacy-relevant data and to prohibit or restrict profiling -Liabilities: i) Maintain a large unlinkability set, ii) Equal distribution of traffic between the potential senders and the potential recipients, iii) Unidirectional pseudonyms should be preferred because omnidirectional pseudonyms are susceptible to profiling -Implementation techniques:

• Anonymizer products, services and architectures: Trusted third parties, Surrogate keys, Onion routing, DC-nets, Mix-nets, Hordes, GAP, Tor, Aggregation Gateway • Pseudonymizer tools: CRM personalisation, Application data management • Track and evident erasers: Spyware detection and removal, Browser cleaning tools [START_REF] Himmel | Method and apparatus for selective caching and cleaning of history pages for web browsers[END_REF], Activity traces eraser, Hard disk data eraser, Use of dummies, Identity Federation Do Not Track Pattern -Related patterns: Undetectability, anonymity

Undetectability

-Definition: Undetectability is the inability for a third party to distinguish who is the user (among a set of potential users) using a service -Problem: The strength of undetectability depends on the number of nodes belonging to the undetectability set -Forces: Enforce users' privacy by allowing them to use a service without being detected by a malicious third party -Benefits: i) Protect users' privacy when using a resource or service by not allowing malicious third parties to detect which services are used by the user, ii) The attacker cannot sufficiently detect whether a particular Item of Interest (IOI) exists or not, e.g. steganography, iii) The attacker cannot sufficiently distinguish whether it exists or not -Liabilities: i) Maintain a large undetectability set, ii) Equal distribution of traffic between the potential senders and the potential recipients -Implementation techniques:

• Administrative tools: Smart cards, Permission management • Information tools: Monitoring and audit tools

• Anonymizer products, services and architectures: Hordes, GAP, Tor • Track and evidence erasers: Spyware detection and removal, Browser cleaning tools, Activity traces eraser, Hard disk data eraser, Identity Federation Do Not Track Pattern • Encryption tools: Encrypting email [START_REF] Bacard | Computer Privacy Handbook: A Practical Guide to E-Mail Encryption, Data Protection, and PGP Privacy Software[END_REF], Encrypting transactions [START_REF] Wells | System and method for message encryption and signing in a transaction processing system[END_REF],

Encrypting documents -Related patterns: Unlinkability, unobservability

Unobservability

-Definition: Unobservability is the inability of a third party to observe if a user (among a set of potential users) is using a service -Problem: The strength of unobservability set depends on the strength of: i)

The sender/recipient anonymity set, ii) The sender/recipient undetectability set -Forces: Users privacy is enforced since they can use a resource or service anonymously and without being detected regarding the service used when the state of IOIs should be indistinguishable from any IOI (of the same type) at all when we want to send messages that are not discernible from e.g. random noise -Benefits: i) Anonymity and Undetectability enforcement per service, ii) Ensures that a user may use a resource or service without others, especially third parties, being able to observe that the resource or service is being used, iii) Requires that users and/or subjects cannot determine whether an operation is being performed -Liabilities: i) Depends on the successful implementation of both anonymity and undetectability, ii) Strong encryption required demanding many resources, iii) Slower communication due to complex calculations -Implementation techniques:

• The implementation of the aforementioned Privacy Process Patterns follows an abstract approach, enabling them to be applied to any requirements engineering methodology. In order to substantiate the applicability and usefulness of the Privacy Process Patterns that have been presented in Section 3, we opted to apply them on a privacy requirements engineering methodology, i.e. PriS (Privacy Safeguard). This methodology incorporates privacy requirements into the system design process and has been developed so as to assist designers on eliciting, modelling, designing privacy requirements of the system to be and also to provide guidance to the developers on selecting the appropriate implementation techniques that best fit the organisation's privacy requirements. PriS provides a set of concepts for modelling privacy requirements in the organisation domain and a systematic way-of-working for translating these requirements into system models, adopting the use of Privacy Process Patterns as a way to i) describe the effect of privacy requirements on business processes and ii) facilitate the identification of the system architecture that best supports the privacy-related business processes. PriS methodology comprises the following four activities that are presented below in an abstract way, as the implementation of them will be thoroughly described in Section 5, through a real case study:

1. Elicit privacy-related goals. This step concerns the elicitation of the privacy goals that are relevant to a specific organisation. It usually involves a number of stakeholders and decision makers (managers, policy makers, system developers, system users, etc.) 2. Analyse the impact of privacy goals on organisational processes. The second step is to analyse the impact of these privacy goals on processes and related support systems 3. Model affected processes using privacy process patterns. Having identified the privacy-related processes, the next step is to model them, based on the relevant privacy process patterns 4. Identify the technique(s) that best support/implement the above process. The final step is to define the system architecture that best supports the privacyrelated process identified in the third step. Again, privacy process patterns are used to identify the proper implementation technique(s) that best support/implement corresponding processes

The proposed framework uses the concept of goal as the central and most important concept. Goals are desired state of affairs that need to be attained. Goals concern stakeholders, i.e. anyone that has an interest in the system design and usage. Also, goals are generated because of issues. An issue is a statement of a strength, weakness, opportunity or threat that leads to the formation of the goal. Privacy is a highly regulated area in Europe. The protection of users' privacy is stated in many European and national legislations through the form of laws, policies, directives, best practices, etc. [START_REF]679 of the European Parliament and of the Council of 27 April 2016 on the protection of natural persons with regard to the processing of personal data and[END_REF]. Thus, legal issues need to be taken under consideration during the identification of functional and nonfunctional requirements. Goal identification needs to take under consideration all these elements before further analysis is conducted.

As shown in Figure 1, there are two types of goals in the proposed framework, namely organisational goals and privacy goals. Organisational goals express the organisation's main objectives that need to be satisfied by the system into consideration. In parallel, privacy goals are introduced because of specific privacy related properties. Through the privacy goals, the realisation of the identified privacy properties is achieved. Thus, all privacy related properties that need to The relationship between goals and subgoals is many to many, in the sense that one goal can be realised from one or more processes and one process can support the realisation of one or more goals.

Expression of PriS with JSON Format

Another reason for choosing PriS in order to apply the proposed structure of the Privacy Process Patterns is their expression of its structure in JSON format [START_REF] Crockford | The application/json Media Type for JavaScript Object Notation (JSON[END_REF] and the reasoning it facilitates through this format. Prior to PriS, the transmission from the design to the implementation phase was vague; developers did not have a methodology to automate this process, i.e. the selection of most suitable privacy enhancing technologies to apply in their context. PriS extended version is expressed in the JSON format, which is an Open Standard used to transmit data objects consisting of attribute-value pairs [START_REF] Mavropoulos | Apparatus: Reasoning About Security Requirements in the Internet of Things[END_REF]. The attribute is immutable and corresponds to the concepts of the model. The suggested patterns are generic enough for being used in every Requirements Engineering method.

The JSON format is an example to represent their ability to link the expressed knowledge in a more structured and closer to programmer format in order to bridge the gap between the design the and the implementation phase. One of the most common issues in the RE world is that developers find hard to implement the design outcomes, especially if these are related to system's non-functional requirements. JSON format assists the developers in the realisation of the identified privacy concerns (requirements) and a way that they can be implemented using a structured low level expression language and not generic/abstract software engineering diagrams. Of course, JSON can be replaced by other structured XML-like formats. However, its wide use and dynamic nature of the template inspired us to express our work using this format. The value is mutable and corresponds to the values assigned based on the analysis of the respective system. JSON template assist on the direction of simplifying the process for the developers of implementing what had been suggested from the design phase, by expressing the conceptual business process in this format. This format is preferable since it can raise developers' awareness in understanding the outcomes of the aforementioned reasoning. Based on the proposed framework, every identified privacy requirement is expressed in a structured textual format using the JSON format. Through this JSON template, a more formalised expression of the whole set of concepts is achieved, and developers can understand the privacy requirements that need to be satisfied and the processes that need to be altered for addressing the privacy properties.

The PriS JSON template, presented in Fig. 2a, is in accordance with the four activities of PriS presented previously. The object Privacy requirement consists of the Title, the Privacy Goal that it wishes to achieve, the specific Organisational Goal that it relates to, the Process, and the Privacy Enhancing Technologies. The organisational goal consists of its Title, its Parent Goal, its Child Goal, and its Decomposition Type. The attribute Process indicates which process is affected. It contains the Title, the Parent Process, the Child Process and finally, the Process Pattern that needs to be satisfied. From the field of process pattern, we realise which privacy pattern we will implement. Finally, the attribute Privacy Enhancing Technologies assists developers on the selection of the set of most appropriate existing privacy enhancing technologies related to the specific privacy properties. Fig. 2b depicts the Privacy Process Pattern template expressed with JSON format, enhancing PriS methodology. The template follows the same structure as it was described in Section 3, containing the fields name, context, problems, forces, benefits, liabilities, implementation techniques, and finally, related patterns. This final field contains all the available techniques that can satisfy the examined privacy requirement. The difference among this field and the one of Privacy Enhancing Technologies, which is included at the general template, is that the first one contains all the potential solutions, where the latter picks only the ones that satisfy the specific organisational goal. The template of the privacy process pattern will be included in the general template of the PriS JSON template to enhance the Process Pattern attribute. A real case study, in which PriS methodology has already been implemented to, and can be used to examine the applicability of the proposed Privacy Process Patterns' template, is the one of Aegean Career Unit. Specifically, University of the Aegean has built a software system for its Aegean Career Office. A detailed description of the Career Office System can be found in [START_REF]ICTE-PAN: Methodologies and Tools for Building Intelligent Collaboration and Transaction Environments in Public Administration Networks[END_REF]. The scope of this case study was the identification of all respective concepts based on the PriS framework for conducting privacy-aware analysis based on the system's context and the stakeholders' requirements. The main objective of the Career Office system of the University of the Aegean is boundary management, i.e. helping students to manage the choices and transitions they need to make on exit from their studies in order to proceed effectively to the next step of their life. The Career Office system is described by three main principles that form the three primary organisational goals, namely: a) Provide Career Information, b) Offer Guidance through Events and c) Maintain a lifelong communication with the graduates. In Fig. 3, the goal model of the examined case study is depicted. We analyse only the principle 'Maintain a lifelong communication with the graduates' for simplicity reasons.

In accordance with the first step of PriS, the main privacy requirement identified along with stakeholders, was the following: "Graduates' anonymity should be enforced when collecting the completed questionnaires". For protecting graduates' privacy, it is of major importance to ensure that all types of analysis and produced results don't lead to any form of privacy violation directly or indirectly. Based on the organisation's context, graduates must be ensured that nobody, es-Fig. 3: Goal model pecially malicious third parties, will be able to reveal the name or other elements that may lead to the identification of the graduate that submits the answered questionnaire; when graduates send information through the career office portal, it must be ensured that others will not be able to reveal any personal identifiable information. Following the identified requirement, the privacy goal that needs to be addressed and fulfilled is the anonymity goal.

Proceeding to the second step of PriS methodology, we need to identify the impact of this goal in the Career Office system, and thus, the identification of the organisational goals and subgoals that deal with the specific requirement is vital. For satisfying the anonymity goal, the main goal, subgoal and process affected are the following:

-Main Goal: Maintain a lifelong communication with the graduates (G3) -Subgoal: Make follow up research concerning the professional progress of the graduates by sending them questionnaires (G 3.3) -Main Process: Conduct Graduates Surveys (P4) -Subprocess: Collect Responses (P 4.3)

The third step of PriS indicates the modelling of the affected processes, using privacy process patterns. For realising the identified privacy goals, the respective processes that implement the privacy-related subgoals were identified. Thus, for the anonymity goal, the respective process that identifies the operationalised subgoal G3.3 is P4 and specifically, the 'P4.3 Collect Responses'. For assisting the realisation of privacy goals on processes, privacy process patterns are introduced. Specifically, for every privacy goal, a respective privacy process pattern may be introduced on to the privacy-aware processes leading to the realisation of the privacy requirements by the respective PET in a more mature and concrete way. By applying the relevant privacy process pattern on the respective privacyrelated process, it is easier for the designer to identify the appropriate PETs, leading to the successful satisfaction of the respective goals. In the anonymity pattern, the user initiates a request for using a service to the system. The system checks the request and proceeds with the decision of preserving user's anonymity (in case the type of service requested should satisfy this privacy goal) or executes the identification task which leads the user to the process of providing their real credentials for granting access to use the requested service. Finally, according to PriS, the final step is the identification of the technique(s) that best support/implement the aforementioned procedures, the designer along with the stakeholders and the organisation's developer team decide the most appropriate PET for realising the identified privacy goals. The definition of selection criteria for the most adequate PET is out of the scope of this paper. In the given scenario, from the different options presented in Fig. 4b, our analysis has identified and suggested to the stakeholders the following PETs, presented in Fig. 4a: Crowds, Onion Routing, Tor and GAP Protocol.

Conclusions

This paper presents a set of privacy process patterns that can be used to bridge the gap between privacy design and implementation, and their instantiation in JSON. These patterns are illustrated using the Career Office system of the University of the Aegean. Although, due to lack of space we have focused on the definition of five patterns, more patterns can be defined using the same template.

Future work includes the development of a privacy pattern language that will further assist developers in building the gap between design and implementation phase. In addition, we are planning to extend our work to elicit and define privacy patterns in new domains, such as Internet of Things and Cloud Computing.

  Administrative tools: Smart cards, Permission management • Anonymizer products, services and architectures: Hordes, GAP, Tor • Track and evidence erasers: Spyware detection and removal, Hard disk data eraser, Identity Federation Do Not Track Pattern -Related patterns: Anonymity, undetectability 4 Privacy Process Patterns Implementation 4.1 PriS methodology

Fig. 1 :

 1 Fig. 1: Conceptual model

Fig. 2 :

 2 Fig. 2: PriS and Privacy Process Pattern JSON template

Fig. 4 :

 4 Fig. 4: Instantiation with JSON

Acknowledgments. This research was partially supported by the Visual Privacy Management in User Centric Open Environments (VisiOn) project, supported by the EU Horizon 2020 programme, Grant agreement No. 653642.


Hongfa Xue

Yurong Chen

Fan Yao

Yongbo Li

Tian Lan

Guru Venkataramani

SIMBER: Eliminating Redundant Memory Bound Checks via Statistical Inference

Unsafe memory accesses in programs written using popular programming languages like C and C++ have been among the leading causes of software vulnerability. Memory safety checkers, such as Softbound, enforce memory spatial safety by checking if accesses to array elements are within the corresponding array bounds. However, such checks often result in high execution time overhead due to the cost of executing the instructions associated with the bound checks. To mitigate this problem, techniques to eliminate redundant bound checks are needed. In this paper, we propose a novel framework, SIMBER, to eliminate redundant memory bound checks via statistical inference. In contrast to the existing techniques that primarily rely on static code analysis, our solution leverages a simple, model-based inference to identify redundant bound checks based on runtime statistics from past program executions. We construct a knowledge base containing sufficient conditions using variables inside functions, which are then applied adaptively to avoid future redundant checks at a function-level granularity. Our experimental results on realworld applications show that SIMBER achieves zero false positives. Also, our approach reduces the performance overhead by up to 86.94% over Softbound, and incurs a modest 1.7% code size increase on average to circumvent the redundant bound checks inserted by Softbound.

Introduction

Many software bugs and vulnerabilities in applications (that are especially written using C/C++) occur due to unsafe pointer usage and out-of-bound array accesses. Security exploits, that take advantage of buffer overflows or illegal memory reads/writes, have been a major concern over the past decade. Some of the recent examples include: (i) In February 2016, a Google engineer discovered a stack overflow bug in the glibc DNS client side resolver inside getaddrinfo() function that had the potential to be exploited through attacker-controller domain names, attacker-controlled DNS servers or man-in-the-middle attack [START_REF]glibc getaddrinfo stack-based buffer overflow[END_REF]; (ii) In 2016, Cisco released security patches to fix a buffer overflow vulnerability in the Internet Key Exchange (IKE) version 1 (v1) and IKE version 2 (v2) code of Cisco ASA Software that could allow an attacker to cause a reload of the affected system or to remotely execute code [START_REF]Cisco ASA Software IKEv1 and IKEv2 Buffer Overflow Vulnerability[END_REF].

In order to protect software from spatial memory/array bound violations, tools such as Softbound [START_REF] Nagarakatte | SoftBound: Highly Compatible and Complete Spatial Memory Safety for C[END_REF] have been developed that maintains metadata such as array boundaries along with rules for metadata propagation when loading or storing pointer values. By doing so, Softbound makes sure that pointer accesses do not violate boundaries through runtime checks. While such a tool offers protection from spatial safety violations in programs, we should also note that they often incur high performance overheads due to the following reasons. a) Array bound checking incurs extra instructions in the form of memory loads and stores for pointer metadata and the propagation of metadata between pointers during assignments. b) In pointer-intensive programs, such additional memory accesses can introduce memory bandwidth bottleneck, and further degrade system performance.

To mitigate runtime overheads, static techniques to remove redundant checks have been proposed., e.g., ABCD [START_REF] Bodík | ABCD: eliminating array bounds checks on demand[END_REF] builds and solves systems of linear inequalities among bound and index variables, and WPBound [START_REF] Sui | Eliminating Redundant Bounds Checks in Dynamic Buffer Overflow Detection Using Weakest Preconditions[END_REF] statically computes the potential range of target pointer values inside loops to avoid Softboundrelated checks. As the relationship among pointer-affecting variables (i.e., variables, whose values can influence pointers) and array bounds become more complex, static analysis is less effective and usually cannot remove a high percentage of redundant array bound checks.

In this paper, we propose SIMBER, a novel approach that verifies conditions for eliminating bound checks on the fly by harnessing runtime information instead of having to rely on discovering redundant checks solely during compiletime or using static code analysis. SIMBER is effective in removing a vast majority of redundant array checks while being simple and elegant. The key idea is to infer the safety of a pointer dereference based on statistics from prior program executions. If prior executions show that the access of array A with length L at index i is within bound, then it is safe to remove the checks on any future access of A with length no smaller than L and an index no larger than i.

In summary, this paper makes the following contributions: 1. Instead of solely relying on static code analysis, SIMBER utilizes runtime statistics to check whether array bound checks can be eliminated. Our experimental results show that SIMBER can discover a high number of redundant bound checks through analyzing the variables that can affect the pointer values.

2. We determine a bound check as redundant only if previous executions deem the checks to be unnecessary and current execution satisfy the condition derived from such prior execution history. This helps SIMBER to guarantee zero false positives.

3. We evaluate using applications from SPEC2006 benchmark suite [1] that have the highest performance overheads in Softbound: bzip2, lbm, sphinx3 and hmmer. In these experiments, we observe that our approach reduces the performance overheads of spatial safety checks by over 86.94% compared to Softbound.

Background

Softbound stores the pointer metadata (array base and bound) when pointers are initialized, and performs array bound checks (or validation) when pointers are dereferenced. For example, for an integer pointer ptr to an integer array in-tArray[100], Softbound stores ptr base = &intArray[0] and ptr bound = ptr base + size(intArray). When dereferencing pointers, Softbound obtains the base and bound information associated with the target pointer ptr, and does the following check: if the value of ptr is less than ptr base, or, if ptr+size is larger than ptr bound, the program terminates. A disadvantage with this approach is the high runtime performance overheads associated with metadata tracking and bound checks especially on pointers that are largely benign or safe. Figure 1 shows the runtime overhead incurred by Softbound-instrumented applications over un-instrumented application as baseline in SPEC2006 benchmarks [1].

We note that some prior works [START_REF] Bodík | ABCD: eliminating array bounds checks on demand[END_REF][START_REF] Sui | Eliminating Redundant Bounds Checks in Dynamic Buffer Overflow Detection Using Weakest Preconditions[END_REF] 2, where f oo(dest, src, n) copies the first n characters in string src to dest, and replaces remaining characters with blocks of 4-character pattern '0000'. To guarantee safe pointer usage, Softbound checks (denoted by CHECK SB) will be added before each pointer dereference, e.g., in lines 8, 9, and 20. Thus, bound checks are performed for each iteration of the for and while loops, resulting in high execution time (performance) overhead.

A static approach such as ABCD [START_REF] Bodík | ABCD: eliminating array bounds checks on demand[END_REF] relies on building constraint systems for target pointers and programs to remove redundant bound checks. In particular, it identifies that indices i and j in f oo() must satisfy i ≤ j from the conditions in line 18. Therefore, bound checks on * (dest+i) in line 8 is deemed redundant given the checks performed on * (dest + j) in line 20. However, such static approaches cannot be effective in eliminating other bound checks where such static inferences cannot be made (e.g.., in lines 9 and 20). Further, bound information for both pointers dest and src needs to be kept and propagated inside f oo() at runtime.

In this paper, we show that (conditionally) removing all the bound checks in foo() is indeed possible using SIMBER. Our solution stems from two key observations. First, redundant bound checks can be effectively identified by examining different runs of f oo(). Consider pointer dereference * (src + i) in line 10 as an example. Let i (k) and src bound (k) denote the value of index i and the bound of array src in the kth run, which is already determined to be boundsafe, i.e., i (k) ≤ src bound (k) . It is easy to see that any future runs of f oo() satisfying i ≤ i (k) and src bound ≥ src bound (k) will also be bound-safe, due to the following chain of inequalities i ≤ i (k) ≤ src bound (k) ≤ src bound, implying i ≤ src bound. Second, through a simple dependency analysis, we find that the value of index i is only positively affected by input variable n. Due to this positive dependency, the redundant-check condition i ≤ i (k) is guaranteed if we have n ≤ n (k) . Thus, bound checks for * (src + i) in line 9 can be determined as redundant by comparing input variables n and src bound with that of previous runs, which entirely removes all checks and bound propagation in f oo() at function-level. It constructs multi-dimensional safe regions where the values of such pointeraffecting variables do not result in bad program behavior (e.g., program crash, buffer overflow). In the current program execution, if the data point representing pointer-affecting variables is inside the safe region, then this pointer dereference is determined to be safe.

1 foo_SB 2 ( char * dest , char * src , int n ) 3 { 4 int i

Dependency Graph Construction

Dependency Graph (DG) is a bi-directed graph G = (V, E) that represents program variables as vertices in V, and models the dependency between the variables and array indices/bounds through edges in E. We construct a DG for each function by including all if its pointers and the pointer-affecting variables that could affect the value of pointer. We add trip count (number of times a branch is taken) as auxiliary variables to assist the analysis of loops.

v 2 if v 1 can affect v 2 .
Abstract Syntax Tree (AST) is commonly used by compilers to represent the structure of program code, and to analyze the dependencies between variables and statements. We use Joern tool [START_REF] Yamaguchi | A Robust Code Analysis Platform for C/C++[END_REF] to generate AST for each function.

Algorithm 1 Dependency graph construction for a given function f oo()

1: Input: source code of function f oo() 2: Construct AST of function f oo() 3: Initialize V = φ, E = φ 4: for each variable v in AST do 5: V = V + {v} 6: for each statement s in AST do 7:
for each pair of variables j, k in s do 8:

add edge e(j, k) to E according to Remark 1 9: Output: Dependency-Graph G = (V, E)

Algorithm 1 shows the pseudo code of Dependency Graph (DG) construction for a given function, f oo(). First, we obtain all of the pointers and their corresponding pointer-affecting variables, and represent them as DG-Nodes. Second, we traverse dependency graph and identify adjacent DG-Nodes that represent the pointer-affecting variables associated with each target pointer. Each target pointer will have an entry in the form of (f unc : ptr, var 1 , var 2 , ..., var n ) where f unc and ptr are the names of the function and target pointer respectively, with var i being the name of pointer-affecting variables associated with ptr. Through logging the values of these variables during program executions, we build conditions to determine safe regions that help eliminate redundant bound checks.

Remark 1. Edges added into Dependency Graph:

E1 Assignment statements A := B B → A E2 Function parameters Func(A,B) B ↔ A E3 Loops for.../while... Add TC to Loops (1) Assignment inside Loops A := B TC → A E4 Array Indexing A[i] i → A

Statistical-guided Inference

This module builds safe regions based on the pointer-affecting variables identified by DGs, and updates the safe region through statistical inference from previous execution. Once the pointer-affecting variables for the target pointer are determined, SIMBER collects the values of pointer-affecting variables from runtime profile, and produces a data point (or a vector) in Euclidean space with the coordinates of data point being the actual values of pointer-affecting variables. The dimension of the Euclidean space is the number of pointer-affecting variables for the target pointer.

The inference about pointer safety (for pointer-affecting variables that are positively-correlated with the array bound) can be derived as follows: Let us say that a data point p = (vp 1 , vp 2 , . . . , vp d ) from prior execution is checked and deemed as safe. Consider another data point q = (vq 1 , vq 2 , . . . , vq d ) for the same target pointer from current execution. If each element of q is no larger than that of p, i.e., vq 1 ≤ vp 1 , vq 2 ≤ vp 2 , . . ., vq d ≤ vp d , then the bound checks on the target pointer can be removed in the current execution. To extend this inference to pointer-affecting variables that are negatively-correlated with array bound, we unify the representation by converting the variable bound into C -bound for sufficiently large constant C (such as the maximum value of an unsigned 32-bit integer). Thus C -bound is also positively correlated, and C -bound q ≤ C -bound p implies bound q ≥ bound p .

Definition 3 (False Positive).

A false positive occurs if a bound check, that is identified as redundant, is indeed necessary and should have not been removed. Definition 4 (Safe Region (SR)). Safe region is an area that is inferred and built from given data points, such that for any point within the region, the corresponding target pointer is guaranteed to have only safe memory access, e.g., all bound checks related to the pointer can be removed with zero false positive, under the assumption that point-affecting variables have monotonic linear relationships with pointer bound.

Thus, the Safe Region derived from a single data point p is the enclosed area by projecting it to each axis. In other words, it includes all vectors that have smaller (pointer-affecting variable) values and are dominated by p. For example, the safe region of a point (3, 2) is all of the points in the euclidian space with the first coordinate smaller than 3 and the second coordinate smaller than 2 in R 2 , namely q = (q 1 , q 2 ) : q 1 ≤ 3, q 2 ≤ 2. We can obtain the Safe Region of multiple data points by taking the union of the safe regions generated by each data point.

Given a set S which consists of N data points in R D , where D is the dimension of data points, we first project point p i , i = 1, 2, . . . , N , to each axis and build N -surface enclosed area in R D , e.g., building a safe region for each data point. The union of these N safe regions is the safe region of S, denoted by SR(S). Thus, if a new data point q falls inside SR(S), we can find at least one existing point p ∈ S that dominates q, i.e., q ≤ p. That is to say, the enclosed projection area of p covers that of q, which means for every pointer-affecting variable in p is larger than that of q.

There are data points that cannot be determined as safe based on existing (current) safe region when q / ∈ SR(S). In this case, SIMBER performs bound checks to determine memory safety of such data points and adaptively updates the safe region based on the outcome. More precisely, given current safe region SR(S) and the new coming data point q / ∈ SR(S), SR(S) will expand to SR(S) by:

SR = SR(S ∪ q) = SR(S) ∪ SR(q) = SR(S) ∪ {x : x ≤ q}, (1)
where {x : x ≤ q} is the set of safe points dominated by vector q. It expands the safe region if (i) there are pointer-affecting variables in the new input q that have a larger value than all points in current safe region SR(S), or (ii) there are array lengths or negatively-correlated variables that have smaller values than all points in SR(S), allowing higher degree of redundant bound check elimination in future executions.

Knowledge Base

SIMBER stores the safe regions for target pointers in a disjoint memory space -Knowledge Base. The data in Knowledge Base, in the format of (key, value), represents the position and the sufficient conditions for removing the redundant bound checks for each target pointer. Statistical Inference is triggered to compute the Safe Region whenever the Knowledge Base is updated with newer data points and new execution logs.

We use SQLite [START_REF]SQLite[END_REF] to store our Knowledge Base. We create a table to store conditions derived from pointer values and the corresponding pointer-affecting variables.

Redundant Checks Identification

SIMBER instruments functions within the program with a call to SIMBER(), that collects pointer-affecting input parameters inside a target function, and queries the knowledge base to obtain the conditions for eliminating array bound checks. In particular, if the all of the data points (formed using function parameters) are within the safe region, the propagation of bound information and the array bound checks can be safely removed from this target function entirely.

We maintain two versions of Check-Hotspot functions: the original version (which contains no bound checks) and the Softbound-instrumented version (that has bound checks and bound meta-data propagation). Based on the result of SIMBER() outcome, we can either skip all bound checks inside the function (if the condition holds) or proceed to call the Softbound-instrumented function (if the condition is not satisfied) where bound checks would be performed as shown in Figure 2. The instrumentation of SIMBER() condition verification inside functions leads to a small increase in code size (by about 1.7%), and we note that such extra code is added only to a small subset of functions with highest runtime overhead for Softbound (see Section 3.5 for details).

Check-HotSpot Identification

To minimize the effect of runtime bound checks, we choose Check-Hotspots functions that have high levels of pointer activity. We identify Check-HotSpots as follows: a) We use Perf profiling tool [START_REF] De Melo | The new linux 'perf' tools[END_REF] to profile two versions of programs: non-instrumented version and softbound-instrumented source code. b) We compute the difference in absolute execution time spent on different functions between non-instrumented source programs and softbound-instrumented programs to capture the extra time spent on softbound-related code. For every function, we calculate the function-level overhead as the ratio of the time spent on softboundrelated code to the total execution time spent in the original version. c) We list all of the functions with function-level overhead of at least 5% as the Check-HotSpots. ure 4. Function SIMBER() verifies whether the input variables of f oo() satisfy the condition to eliminate array bound check, and chooses one of the two possible branches accordingly. Recall the Softbound-instrumented foo() function in Figure 2. The dependency graph contains edges from n to i (due to the for loop in line 6), from src len to len (due to the assignment in line 14), from len to i (due to the while loop in line 16), from i to j (due to the second for loop in line 18), and from i, j to pointers src and dest (due to pointer dereference in lines 10 and 21).

SIMBER-optimized Softbound Code

SIMBER instruments the program by adding two branches as shown in Fig-

We focus on bound checks for * (dest + j) in line 20 to illustrate SIMBER. From the dependency graph, we find bound-affecting variables len and n, and version (denoted as Softbound). b) SIMBER-Optimized Softbound (denoted as S.O.S), where redundant bounds check are removed.

Based on our Check-HotSpot identification results, we study 8 functions shown in Table 1. We note that some Check-HotSpot functions may contribute to high runtime overhead mainly because they are executed frequently, e.g., bzip2::mainGtU is called more than 8 million times, despite having small code footprint.

Redundant Checks

To illustrate SIMBER's efficiency in eliminating redundant bounds checks, Table 1 shows the number of array bound checks required by Softbound, and the number of redundant checks removed by SIMBER along with rate of false positives reported under S.O.S. Our results show that Softbound-related checks can be completely eliminated by S.O.S in three out of eight cases. 2 shows the execution time incurred by Check-Hotspot functions in Softbound and S.O.S. Our experiments show that upto 86.94% improvement in execution time overhead can be achieved by S.O.S through eliminating redundant array bound checks inserted by Softbound. In a few functions, despite totally eliminating Softbound-instrumented array bound checks, a small runtime overhead is still incurred due to the extra code added by SIMBER to circumvent redundant bound checks at the function-level.

Memory overhead and code increase

We note that SIMBER's memory overhead for storing Knowledge Base and additional code instrumentation are modest. Our experiments show that the worst memory overhead is only 20KB, and the maximum code size increase is less than 5%. Across all applications, SIMBER has an average 5.28KB memory overhead with an average 1.7% code increase. Overall, we reduce memory overhead by roughly 50% compared to that of Softbound.

Case Studies

bzip2 bzip2 is a compression program to compress and decompress inputs files, such as TIFF image and source tar file. We use the function bzip2::mainGtU as an example to illustrate how SIMBER removes redundant bound checks. Using Dependency Graph, we first identify nblock, i 1 , and i 2 as the pointeraffecting variables for the target buffer pointer. For each execution, the Statistical Inference module computes and updates the Safe Region, which results in the following (sufficient) conditions for identifying redundant bounds checks in bzip2::mainGtU :

nblock > i 1 + 20 or nblock > i 2 + 20 (2)
Therefore, every time this check-hotspot function is called, SIMBER will eliminate bound checks if the inputs variables' values: nblock, i 1 , and i 2 satisfy the conditions above. Because its safe region is one-dimensional, the condition checks have low runtime overhead. If satisfied, the conditions guarantee a complete removal of bounds checks in bzip2::mainGtU function.

As a second example in bzip2::generateMTFValue, we study the conditions to remove bound checks on five different target pointers inside of the function. We observed that three out of five target pointers, with constant array length, are relatively safe from out-of-bound accesses that may also be handled through static (pre-runtime) methods. The array bounds for the other two target pointers are not constant, and eliminating redundant checks on these pointer require a more careful consideration of runtime statistics and conditions formed using pointer-affecting variables. We note that bzip2::BZ2 decompress also has similar behavior.

hmmer hmmer is a program for searching DNA gene sequences, and involves many double pointer operations. There is only one Check-HotSpot function, P7Viterbi, which contributes over 98% of the performance overhead.

Inside of the hmmer::P7Viterbi function, there are four double pointers: xmx, mmx, imx and dmx. To cope with double pointers in this function, we consider the row and column array bounds separately, and construct safe regions for each dimension. Besides the four double pointers, we also identify conditions for identifying redundant bound checks for another 14 one-dimensional arrays and pointers. In this case, SIMBER is able to eliminate most of the redundant checks for these 14 one-dimensional arrays with relatively simple conditions for bound check removal. However, for the four double pointers, SIMBER is slightly more conservative due to higher number of dimensions in the conditions. lbm lbm is developed to simulate incompressible fluids in 3D, and has only one Check-HotSpot function: lbm::LBM performStreamCollide. The function has two pointers (as input variables) with pointer assignments and dereferencing inside of a for loop. Using SIMBER, we obtain the bound conditions for each pointer dereferencing. Using runtime profile, we observed that the pointer dereferences to the same set of memory addresses repeatedly, providing an opportunity to remove all of the bound checks after successfully verifying bound conditions in the first iteration.

sphinx3 Sphinx3 is a well-known speech recognition system. For the first Check-HotSpot function sphinx3::vector gautbl eval logs3, there are four target pointers inside this function. Due to the identical access pattern, once we derive the bound check removal conditions for one single pointer, it can also be used for all others, allowing for the redundant checks to be eliminated simultaneously in this function. We observed a similar behavior for a second Check-HotSpot function sphinx3::mgau eval.

The last function sphinx3::subvq mgau shortlist also has four target pointers. For this function, SIMBER only removed 18.1% redundant checks. On further investigation, we found that a pointer, named vqdist, inside of this function had indirect memory access with its index value derived from another pointer: map. To handle such situations, we note that our DGs can be extended to include dependencies resulting from such indirect pointer references. Since we do not handle indirect memory accesses in the current version, we are unable to eliminate any redundant bound check that Softbound may perform for this pointer.

Related Work

Static code analysis and tools has been widely studied for discovering program vulnerabilities and bugs [20] [8]. Nurit et al. [START_REF] Dor | CSSV: Towards a realistic tool for statically detecting all buffer overflows in C[END_REF] have studied techniques that target string-related bugs in C programs with conservative pointer analysis using abstract constraint expressions for pointer operations. Such static approaches require extensive program modeling and analysis (e.g., by constructing constraint solver systems) and may offer limited scope in dealing with certain vulnerabilities that occur only at runtime (e.g., due to user input-related bugs). Wurthinger et al. [START_REF] Würthinger | Array bounds check elimination for the Java HotSpot client compiler[END_REF] use dominator tree to maintain the conditions for code blocks in Javabased programs. CCured [START_REF] Necula | CCured: Type-safe retrofitting of legacy code[END_REF] is a type-safe system that classifies pointers to three types: safe, sequence, dynamic, and then applies different rules to check them. Different from these prior works, SIMBER leverages runtime profile to determine safe pointer accesses.

Statsym [START_REF] Fan | Stat-Sym: Vulnerable Path Discovery through Statistics-guided Symbolic Execution[END_REF] proposes a novel framework to combine statistical and formal methods to discover for vulnerable paths in program, and can dramatically reduce the search space for vulnerable paths compared to symbolic executors such as KLEE [START_REF] Cadar | Unassisted and automatic generation of high-coverage tests for complex systems programs[END_REF]. Additionally, some works employ machine learning to improve the efficiency of static code analysis, and use the similarity of code patterns to facilitate discovery of bugs and errors [START_REF] Yamaguchi | Chucky: Exposing missing checks in source code for vulnerability discovery[END_REF] [START_REF] Yamaguchi | Generalized vulnerability extrapolation using abstract syntax trees[END_REF]. We note that the accuracy of such methods rely on the choice of machine learning algorithms. Hardware support to identify malicious information outflows [START_REF] Venkataramani | Detecting Hardware Covert Timing Channels[END_REF] and code reuse-based attacks [START_REF] Yao | Jop-alarm: Detecting jump-oriented programming-based anomalies in applications[END_REF] through buffer overflows have also been studied by prior works. SIMBER can work synergistically with these approaches to improve the security of applications.

Conclusions and Future Work

In this paper, we propose SIMBER, a framework integrating with statisticsguided inference to remove redundant array bound checks based on runtime profile. Its statistical inference adaptively builds a knowledge base using program execution logs containing variables that affect pointer values, and then uses this information to remove redundant array bound checks inserted by popular array bound checkers such as Softbound. SIMBER reduces performance overhead of Softbound by up to 86.94%, and incurs a modest 1.7% code size increase on average to circumvent redundant bound checks inserted by Softbound. Currently, SIMBER works at function-level granularity. For future work, we will study ways to deploy SIMBER at a finer granularity to remove redundant bound checks.

Fig. 2 :

 2 Fig. 2: Example code illustrating bound checks performed by SoftBound

Fig. 3 :

 3 Fig. 3: SIMBER Overview and Key Modules

Table 1 :

 1 Redundant array bound checks in Check-HotSpot functions

	Benchmark::Function Name # bounds checks # Redundant checks False Positives
	bzip2::generateMTFValues	2,928,640	1,440,891 (49.2%)	0 (0.0%)
	bzip2::mainGtU	81,143,646	81,136,304 (99.9%)	0 (0.0%)
	bzip2::BZ2 decompress	265,215	196,259 (74.0%)		0 (0.0%)
	hmmer::P7Viterbi	176,000,379	124,960,267 (71.0%)	0 (0.0%)
	lbm::LBM performStreamCollide	128277886	128277886 (100.0%)	0 (0.0%)
	sphinx3::vector gautbl eval logs3	2,779,295	2,779,295 (100.0%)	0 (0.0%)
	sphinx3::mgau eval	725,899,332	725,899,332 (100.0%)	0 (0.0%)
	sphinx3::subvq mgau shortlist	24,704	4,471 (18.1%)		0 (0.0%)
		Time spent in
	Function name	Softbound S.O.S Execution time Reduction
	bzip2::generateMTFValues	77.21s	39.46s	48.89%
	bzip2::mainGtU	47.94s	6.26s	86.94%
	bzip2::BZ2 decompress	35.58s	9.10s	74.42%
	hmmer::P7Viterbi	3701.11s 812.91s	78.04%
	lbm::LBM performStreamCollide 1201.79s 407.06s	66.13%
	sphinx3::vector gautbl eval logs3 1580.03s 318.10s	79.87%
	sphinx3::mgau eval	1582.68s 473.10s	70.11%
	sphinx3::subvq mgau shortlist	270.84s 221.81s	18.1%

Table 2 :

 2 Execution time improvement for Check-HotSpot functions Table

ACKNOWLEDGMENTS

This work was supported by the US Office of Naval Research (ONR) under Award N00014-15-1-2210. Any opinions, findings, conclusions, or recommendations expressed in this article are those of the authors, and do not necessarily reflect those of ONR.

Fig. 4: SIMBER optimized code that determines if bound checks can be removed at function-level granularity form a 3-dimensional vector (len, n, C -dest bound) (for large enough, constant C) to represent the safe region corresponding to bound checks for * (dest + j). Assume that C is 1024 and that three previous data points are available: P 1 = (200, 160, 1024-256), P 2 = (180, 120, 1024-256) and P 3 = (150, 140, 1024-512), respectively. Per our discussion in Section 3.2, a safe region can be derived from the three data point vectors in a R 3 space, i.e., SR = {x : x ≤ P i , ∀i = 1, 2, 3}, where inequality x ≤ P i between two vectors is component-wise.

In future executions, new input variables y = (len, n, C -dest bound) are verified by SIM BER() to determine if vector x is inside this safe region, i.e., y ∈ SR. As long as we can find one vector from P 1 , P 2 and P 3 that dominates y, then the memory access of * (dest + j) in line 20 is safe, allowing us to remove all bound checks and propagation.

Evaluation

We use Softbound as the baseline to evaluate the effectiveness of SIMBER in removing redundant bound checks. All measurements are made on a 2.54 GHz Intel Xeon(R) CPU E5540 8-core server with 12 GByte of main memory. The operating system is ubuntu 14.04 LTS.

We select several applications from SPEC 2006 benchmark suite [1] with high performance overheads, including bzip2, hmmer from SPECint and lbm, sphinx3 from SPECfp. In the evaluation, we first instrument the applications using Softbound, and use Perf [START_REF] De Melo | The new linux 'perf' tools[END_REF] to identify the Check-HotSpot functions. Similar to ABCD [START_REF] Bodík | ABCD: eliminating array bounds checks on demand[END_REF], we consider the optimization of upper-and lower-bound checks as two separate problems. In the following, we focus on eliminating redundant upperbound checks, and we note that this approach can be adapted to the dual problem of lower-bound checks. We use reference inputs provided with SPEC benchmarks. For applications that do not provide developer-supplied representative test cases, we note that fuzzing techniques [START_REF] Mcnally | Fuzzing: the state of the art[END_REF] [16] can be used to generate test cases. The policies considered in our evaluation are a) Softbound-instrumented