Piergiorgio Ladisa
email: piergiorgio.ladisa@sap.compiergiorgio.ladisa@irisa.fr

Henrik Plate
email: henrik.plate@sap.com

Matias Martinez
email: matias.martinez@uphf.fr

Olivier Barais
email: olivier.barais@irisa.fr

Serena Elisa Ponta
email: serena.ponta@sap.com

Towards the Detection of Malicious Java Packages

Keywords: Open-Source Security, Supply Chain Attacks, Malware Detection ACM Reference Format:

Open-source software supply chain attacks aim at infecting downstream users by poisoning open-source packages. The common way of consuming such artifacts is through package repositories and the development of vetting strategies to detect such attacks is ongoing research. Despite its popularity, the Java ecosystem is the less explored one in the context of supply chain attacks.

In this paper, we present simple-yet-effective indicators of malicious behavior that can be observed statically through the analysis of Java bytecode. Then we evaluate how such indicators and their combinations perform when detecting malicious code injections. We do so by injecting three malicious payloads taken from realworld examples into the Top-10 most popular Java libraries from libraries.io.

We found that the analysis of strings in the constant pool and of sensitive APIs in the bytecode instructions aid in the task of detecting malicious Java packages by significantly reducing the information, thus, making also manual triage possible.

CCS CONCEPTS

• Security and privacy → Malware and its mitigation.

INTRODUCTION

Today's software supply chains make extensive use of open-source components. Despite the clear advantages, the lack of transparency and reliance on unknown stakeholders and systems pose several risks.

Open-Source Software (OSS) supply chain attacks are characterized by the injection of malicious code into open-source components as a means for spreading malwares and there exist many attack vectors [START_REF] Ladisa | SoK: Taxonomy of Attacks on Open-Source Software Supply Chains[END_REF][START_REF] Ohm | Backstabber's Knife Collection: A Review of Open Source Software Supply Chain Attacks[END_REF]. Package repositories for OSS (e.g., npm, PyPI, Maven Central) are commonly used by developers to consume OSS packages and several scientific works focus on vetting mechanisms at scale. Most of those tackle interpreted languages (e.g., JavaScript), whereas the Java ecosystem is less explored despite its popularity [START_REF]The State of the Octoverse[END_REF][START_REF]TIOBE Index[END_REF].

Based on the study of real-world attacks, our goal is to find and evaluate simple-yet-effective indicators of malicious behavior in Java packages that can help in filtering out the non-malicious ones. Since the usual way of consuming such packages is through precompiled JARs, we focus on Java bytecode. Indicators of malicious behavior can be used by package repositories vetting the submitted packages or by downstream users checking the downloaded dependencies.

We set out to answer the following research questions: RQ1 -What are possible simple and effective indicators of malicious behavior that can be observed from the bytecode?

RQ2 -How do these indicators and their combinations perform in the detection of malicious Java packages?

To answer those questions we analyze both the constant pool (e.g., to detect obfuscated strings) and bytecode instructions (e.g., to detect sensitive APIs). We assess the performance of the identified indicators by analyzing the Top-10 Java projects from libraries.io 1 , both the original, benign ones as well as infected ones, containing malicious payloads taken from three real-world attacks.

The remainder of the paper is organized as follows. Section 2 presents related works. Section 3 motivates the need for improving the detection of malicious Java Archive (JAR)s in the context of OSS supply chain attacks. Section 4 describes background information. Section 5 presents our static analysis of Java Virtual Machine (JVM) bytecode and answers to RQ1. Section 6 answers RQ2 by evaluating the indicators of malicious behavior in the Java bytecode. Section 7 discusses the limitations of our approach, while Section 8 highlights the conclusions and discusses future works.

RELATED WORKS

Table 1 shows work to date on the detection of malicious opensource packages.

Sejfia et al. [START_REF] Sejfia | Practical Automated Detection of Malicious npm Packages[END_REF] propose a machine learning-based approach for the automated detection of malicious npm packages trained on a labeled dataset. We port some of the considered features in the context of Java, in particular the concept of sensitive APIs (e.g., process creation, dynamic code generation) and the usage of Shannon entropy to detect obfuscation. While they apply the latter at the file level to detect the presence of compiled or minified code, we apply it to the strings found in the Java class file's constant pool.

Vu et al. [START_REF] Vu | LastPyMile: Identifying the Discrepancy between Sources and Packages[END_REF] analyze the discrepancy between source code and the deployed package in PyPI as a way to detect malicious injections in the Python ecosystem. Scalco et al. [START_REF] Scalco | On the feasibility of detecting injections in malicious npm packages[END_REF] perform the same in the context of JavaScript. Conversely, we do not consider the source code.

Duan et al. [START_REF] Duan | Towards Measuring Supply Chain Attacks on Package Managers for Interpreted Languages[END_REF] propose a classifier based both on dynamic and static analysis to classify packages in npm, PyPI, and RubyGems. Among the selected features for the static analysis, they also suggest considering sensitive APIs and to perform data flow analysis to highlight dangerous flows.

Ohm et al. [START_REF] Ohm | Towards Detection of Software Supply Chain Attacks by Forensic Artifacts[END_REF] leverage sandboxes to collect forensic artifacts related to the execution of malicious JavaScript and Python packages and describe the observed dynamic behaviors. In another work [START_REF] Ohm | Supporting the Detection of Software Supply Chain Attacks through Unsupervised Signature Generation[END_REF] they propose a clustering model based on signatures produced from the Abstract Syntax Tree (AST) of malicious JavaScript samples. Our approach is instead only static and focuses on Java.

Garret et al. [START_REF] Garrett | Detecting Suspicious Package Updates[END_REF] propose an anomaly detection approach based on the observation of code features in JavaScript (e.g., opening of connections, read/write to the file system).

Fass et al. [START_REF] Fass | Jast: Fully syntactic detection of malicious (obfuscated) javascript[END_REF] extract features from the AST of JavaScript codes to build a classifier capable of detecting obfuscation.

In the scope of Java malware detection, related works focus on the detection of malicious code in applets or purely malicious JARs (i.e., containing mostly malicious code).

Schlumberger et al. [START_REF] Schlumberger | Jarhead analysis and detection of malicious java applets[END_REF] propose a static approach for applets based on machine learning. Among the selected features they consider sensitive APIs (e.g., for obfuscation and code behavior). Compared to their work, our focus is on OSS packages that may contain a small portion of malicious code, while malicious applets do not need to piggyback on existing benign functionalities. In addition, some of the APIs for applets are not relevant in the scope of Java libraries (e.g., APIs for MIDlets).

Pinheiro et al. [START_REF] Pinheiro | Antivirus applied to JAR malware detection based on runtime behaviors[END_REF] propose a dynamic approach for the automated detection of malicious JARs. They extract forensic features related to the execution of the purely malicious samples in a sandboxed environment to train a classifier based on artificial neural networks. Instead, we perform a static analysis of packages where malicious code was injected.

Other relevant works come from the Android ecosystem [START_REF] Arshad | Android malware detection & protection: a survey[END_REF][START_REF] Batyuk | Using static analysis for automatic assessment and mitigation of unwanted and malicious activities within Android applications[END_REF][START_REF] Li | On locating malicious code in piggybacked android apps[END_REF][START_REF] Ma | Droidetec: Android malware detection and malicious code localization through deep learning[END_REF], especially the ones about the static inspection of Dalvik bytecode. In this case, Aafer et al. [START_REF] Aafer | Droidapiminer: Mining api-level features for robust malware detection in android[END_REF] analyze Android malware samples to extract their commonly used APIs, then build a KNN classifier. As opposed to their work, not having many malicious samples available, our search for relevant APIs is based on the manual inspection of malicious packages. Specific aspects of the Android ecosystem make the problem of detecting malicious Java libraries different. On the one hand, because malware running on mobile devices has different objectives, e.g., financial gain by sending SMS or reading contacts. On the other hand, because there are technical differences between Java for Android and the JVM (e.g., permissions, intents, or APIs existing only for Android).

Reference

Year R u b y P y t h o n J a v a S c r i p t J a v a * Sejfia et al. [START_REF] Sejfia | Practical Automated Detection of Malicious npm Packages[END_REF] 2022 ✓ Scalco et al. [START_REF] Scalco | On the feasibility of detecting injections in malicious npm packages[END_REF] 2022 ✓ Duan et al. [START_REF] Duan | Towards Measuring Supply Chain Attacks on Package Managers for Interpreted Languages[END_REF] 2021 ✓ ✓ ✓ Vu et al. [START_REF] Vu | LastPyMile: Identifying the Discrepancy between Sources and Packages[END_REF] 2021 ✓ Ohm et al. [START_REF] Ohm | Towards Detection of Software Supply Chain Attacks by Forensic Artifacts[END_REF] 2020 ✓ ✓ Ohm et al. [START_REF] Ohm | Supporting the Detection of Software Supply Chain Attacks through Unsupervised Signature Generation[END_REF] 2020 ✓ Garret et al. [START_REF] Garrett | Detecting Suspicious Package Updates[END_REF] 2019 ✓ Fass et al. [START_REF] Fass | Jast: Fully syntactic detection of malicious (obfuscated) javascript[END_REF] 2018 ✓ Table 1: Ecosystems covered by recent scientific works on the detection of malicious open-source packages. ( * ): here we intend the case of JVM bytecode

MOTIVATION

The motivations for our work in detecting malicious Java packages are as follows. First, attacks on the OSS supply chain, characterized by insertions of malicious code into benign packages (cf. Section 3.1) are relevant and increasing [START_REF] Ohm | Backstabber's Knife Collection: A Review of Open Source Software Supply Chain Attacks[END_REF]. Second, the Java ecosystem is important in practice but little discussed in the scientific literature about OSS supply chain attacks (cf. Table 1). Third, the detection rate of common AV solutions for malicious OSS packages is low (cf. Section 3.2).

Open-Source Software Supply Chain Attacks

Listing 1: Malicious code snippet from HttpServlet.java contained in com.github.codingandcoding:servlet-api@3.2.0 As demonstrated by multiple examples of malicious OSS packages [START_REF] Ohm | Backstabber's Knife Collection: A Review of Open Source Software Supply Chain Attacks[END_REF], most of them prove to have a small fraction of harmful code hidden in a bigger corpus of legitimate code. This is similar to the case of piggybacking in Android malwares, where a legitimate application (carrier) is repackaged by grafting a malicious code (rider) [START_REF] Batyuk | Using static analysis for automatic assessment and mitigation of unwanted and malicious activities within Android applications[END_REF][START_REF] Li | On locating malicious code in piggybacked android apps[END_REF][START_REF] Ma | Droidetec: Android malware detection and malicious code localization through deep learning[END_REF].

Listing 1 shows the malicious code snippet present in the package com.github.codingandcoding:servlet-api@3.2.0. Its source version consists of 149 files, 77 of which are in java format and a total of 13458 Lines Of Code (LOC). The malicious payload is present in only one line of code of the file HttpServlet.java, which consists of a total of 749 LOC.

VirusTotal Scan

To understand how common Antiviruses (AVs) perform in the case of malicious packages (i.e., packages where only a fragment of code is malicious), we submitted all the available samples in Backstabber's Knife Collection (BKC) (cf. Section 4.2) to VirusTotal (VT) 2 . Though our focus is Java, we used all samples in BKC as only 4 Java malicious packages are contained and, to the best of our knowledge, no other source of malicious packages for Java is available.

VT allows getting the result of the scan with ~70 AVs for a submitted file [START_REF]Analyses[END_REF][START_REF]Get a URL/file analysis[END_REF]. When requesting the scan of a file, the related response contains the number of AVs that do not detect the sample (U), classify it as malicious (M), do not support the file (TU), fail when analyzing the file (F), and reach a timeout during the analysis (T). Table 2 reports the average result (percentages) of the scan performed on BKC.

Ruby is the ecosystem with the highest percentage of AVs correctly recognizing malicious packages. This can be partly because most of these samples come from the same campaign (i.e., contain the same malicious content).

Overall, we detect a low level of classification as malicious, in particular in Java where only 3% of AVs classify the samples as malicious. Keeping into account the reporting year of the packages that no Antivirus (AV) flagged as malicious, we observe that 278 malicious packages were reported more than two years ago and 45 are older than 5 years, and still they are not detected by AVs. Except for cases where the AVs do not support the provided files, we cannot conclude what causes the low detection (e.g., signatures not present in AV databases) as the internal approaches for most of the AVs are not publicly available.

Type of Responses

BACKGROUND

This section describes the Java class file format and highlights the main features of malwares in the scope of OSS supply chain attacks.

Java class file format

In Just-In-Time (JIT) compilation, the Java source code is compiled into a class file, which contains a platform-independent intermediate representation that is transformed into machine code by the JVM.

Each bytecode instruction consists of a one-byte opcode followed by zero or more bytes for the operands [START_REF]The Java Virtual Machine Instruction Set[END_REF].

When the operands are constants, they are represented by symbolic information contained in the constant pool. The latter act as a symbol table and each element is characterized by index, type, and value. Constant pool entries of type Utf8 hold constant string values. Constants with types such as String, Class, or MethodRef contain instead the index value pointing to the associated Utf8 entry. Figure 1 shows an example of such indexing mechanism.

Constant pool: #1 = Class #2 #2 = Utf8 com/example1/

Backstabber's Knife Collection

Backstabber's Knife Collection [START_REF]Backstabber's Knife Collection[END_REF] is a dataset of malicious OSS packages distributed via popular package repositories in real-world attacks. Samples are collected manually and contributed voluntarily by the community. At the time of writing (July 2022), BKC counts a total of 2886 samples from different ecosystems: 813 in Ruby, 261 in Python, 1807 in JavaScript, and 4 in Java.

Based on the analysis of the BKC, Ohm et al. [START_REF] Ohm | Backstabber's Knife Collection: A Review of Open Source Software Supply Chain Attacks[END_REF] identify the following primary objectives in OSS supply chain attacks and they constitute the types of malware in the scope of our analysis.

A Reverse shell spawns a shell process and redirects both its input and output through an open socket to the attacker machine.

Droppers connect to an attacker-controlled host to download a second-stage payload that will be then executed. The remote payload can be read directly through the connection or be temporarily stored in a local file.

Data exfiltration (most common behavior [START_REF] Ohm | Backstabber's Knife Collection: A Review of Open Source Software Supply Chain Attacks[END_REF]) reads sensitive files as well as environment information and sends it to a remote endpoint.

Denial of Service (DoS) is typically achieved either through resource exhaustion (e.g., fork-bombs) or by deleting system files.

Financial gain is achieved by executing crypto miners in the target system. We consider the case of stealing cryptocurrencies belonging to the category of data exfiltration.

Behaviors Classes

Execution Connection File Input File Output Reading Environment 3: Behaviors required by malwares in our scope to achieve their primary objectives.

Reverse Shell ✓ ✓ Dropper ✓ ✓ ✓ Data Exfiltration ✓ ✓ ✓ DoS ✓ ✓ Financial Gain ✓ ✓ Table

Manual Malwares Inspection

To find relevant indicators of malicious JARs, we start by inspecting the four Java samples from the BKC [START_REF] Ohm | Backstabber's Knife Collection: A Review of Open Source Software Supply Chain Attacks[END_REF]. Two of them are different versions of the same package, and their malicious payload is identical. Because of the scarcity of malware samples in Java, we also analyzed some examples written in other programming languages and ported their code to Java.

We observe that the strings contained in the malwares may contain shell commands, URLs, or paths to sensitive files either in an encoded format (e.g., base64) or unencoded.

The inspection of the Java samples and ported versions from other languages also allowed us to collect some of the Java APIs required to implement the malicious functionalities. We augment such a list by searching in the Java SE documentation [START_REF]Java Platform, Standard Edition Documentation[END_REF] for similar APIs to accomplish the same tasks. We categorize the sensitive APIs according to the behaviors (cf. Table 3) used by the malware types described in Section 4.2. The entire list of Java APIs is available in Table 7, Appendix C.

We also observe that in many samples the malicious code is included in a single method and usually within a try block associated with an empty catch. This suggested implementing an intra-procedural data-flow analysis and looking for such try-catch blocks.

Constant Pool Analysis

Since malwares can contain hardcoded strings, the extraction and analysis of strings is a common practice in malware analysis to obtain evidence about malicious behavior [START_REF] Sikorski | Practical malware analysis: the handson guide to dissecting malicious software[END_REF].

In our work, we extract strings from the constant pool of each class composing the analyzed JAR using the indexing mechanism described in Section 4.1. In the following we present different approaches to detect suspicious strings, highlighting their benefits and limitations.

Entropy Analysis. In information theory, entropy measures the average level of information associated with the possible outcomes of a random variable [START_REF] Elwood | A mathematical theory of communication[END_REF].

To detect the presence of obfuscation (e.g., base64) we measure the Shannon entropy of each string (independent of one another). In fact, obfuscated strings usually have higher entropy than their unencoded counterpart due to their higher variability. For example, bash has an entropy value of 2, while its base64 encoding (i.e., YmFzaA==) has a value of 2.75. However, short strings and small alphabets (e.g., base16), due to their low variability, could lead the Shannon entropy approach to fail in identifying malicious strings.

Since the constant pool often contains log messages for the user, usually in English, we also consider a filtering mechanism based on a measure of relative entropy, such as the Kullbac-Leibler divergence [START_REF] Kullback | On information and sufficiency[END_REF]. The latter measures the distance between two probability distributions. In our context, we measure the distance between the probability distribution of the characters of a supplied string and the one of the characters in the English language. This approach is limited to detect phrases in English and, additionally, URLs containing English words (e.g., domain names) would be filtered out because they have a probability distribution similar to the one of the English language.

Language-Based Filtering. To solve the problem of filtering out strings that resemble sentences we also consider a probabilistic detection of the language by using the Compact Language Detector (CLD2) [START_REF]Compact Language Detector 2[END_REF]. The main benefit of this approach, compared to the one based on the relative entropy described above, is that in this case, we would also remove output messages in languages other than English.

Before checking the detection value of a given string, we make it lower case, tokenize it with NLTK 3 , and remove all the nonalphanumerical characters and the duplicates. Two examples are provided in Listing 4, Appendix B.

If a language is detected, then the string is filtered out. Thus, we consider suspicious those where the language detection failed.

Sensitive Keywords. From the inspection of the BKC we observe that many payloads contain keywords related to bash commands (e.g., bash) or sensitive files (e.g., .bash_history, .ssh) [START_REF] Ohm | Backstabber's Knife Collection: A Review of Open Source Software Supply Chain Attacks[END_REF]. Those are strong indicators of malicious behavior.

To detect such keywords we have built an extensive list from offensive security cheat sheets [START_REF]Local File Inclusion[END_REF]9]. It covers the most popular ways of creating reverse shells, e.g., via bash, netcat, python, or perl. Regarding data exfiltration, it also covers common directories used when testing for Local File Inclusion (LFI) vulnerabilities, e.g., /etc/passwd. Also included are popular domains used for IP lookups (e.g., whatismyip.org), and the keywords https:// and http:// to detect URLs.

The entire corpus of 178 keywords is stored in unencoded format, in different encodings (base64, base32, base16, a85, b85, rot-13, uuencode and url-encoding), and in reverse order (e.g., hsab for bash). When analyzing given JARs, we search for the presence of those keywords in constant pool strings.

Bytecode Instructions Analysis

The analysis of bytecode instructions aims at collecting pieces of evidence of malicious behavior from the operations of a Java program.

Sensitive APIs . As described in Section 5.1, the malwares in scope require execution, networking, file I/O, and the read of environmental information to achieve their goal. Using the list of sensitive Java APIs related to these behaviors presented in Section 5.1 (cf. Table 7, Appendix C), we inspect the bytecode instructions to detect their invocation (e.g., via invokespecial or invokevirtual). In our analysis we only consider native Java APIs to evaluate if this is sufficient to detect the malicious samples.

Execution APIs provide the ability to run shell commands or to evaluate scripts, possibly in other languages than Java [START_REF]The Java Scripting API -Java Documentation[END_REF]. These APIs potentially allow any shell command to be executed. Therefore, an attacker can achieve any malicious behavior through these methods as long as the specified payload is compatible with the system executing it.

Connection APIs provide networking capabilities. They allow the creation of sockets and the redirection of inputs and outputs in the case of a reverse shell. Droppers need also to connect to remote servers to download second-stage payloads. A connection is also required for data exfiltration to send the stolen information to the attacker.

Dynamic Programming APIs leverage Java reflection [START_REF] Mccluskey | Using Java Reflection[END_REF] to load classes and execute their methods at runtime. From the perspective of droppers, an attacker can host a malicious class remotely and have the victim use it via reflection. Reflection makes it harder for the static analyzer to detect the presence of critical APIs. 3 https://www.nltk.org/ Encoding and Cryptographic APIs can be used to obfuscate code to evade detection by AVs. Nearly half of the samples of the BKC use this technique, the most common encoding being Base64 [START_REF] Ohm | Backstabber's Knife Collection: A Review of Open Source Software Supply Chain Attacks[END_REF].

Evironment Reading APIs are relevant in the case of data exfiltration, e.g., to read environment variables, user name, or hostname.

Empty Catch Clauses. Most API calls listed in Table 7, Appendix C throw exceptions to the runtime system [START_REF]What Is an Exception? -Java Documentation[END_REF].

To not alert the victim with a message in case of error or halt program execution altogether, malware developers often include the malicious code within a try block associated with an empty catch block (cf. Listing 3, Appendix A).

Therefore, for each class, we report all the empty catch blocks and in which method they are present. We then scan the instructions of the corresponding try block to search for the presence of sensitive API calls.

Data Flow Analysis. To increase the confidence in detecting malicious JARs, we complement the detection of sensitive APIs with data flow analysis. The goal is to detect cases where malicious payloads flow into sensitive APIs. We carry out an intra-procedural analysis (implemented with ASM [START_REF] Bruneton | ASM 3.0 A Java bytecode engineering library[END_REF]) by interpreting the instructions and by simulating the JVM stack. Once we reach the sensitive API we check the top of the stack to extract the value of the payload.

Response to RQ1

We consider the following indicators as relevant from a security perspective. Constant pool: the presence of high-entropy strings, sensitive keywords (e.g., shell commands), and strings for which no language can be determined. Bytecode instructions: the presence of sensitive APIs (execution, networking, file i/o, environment reading, dynamic programming, and encoding/cryptographic), especially in combination with empty catch clauses and the use of string literals defined in the same respective method.

EXPERIMENT

In this section, we describe the experiment to assess the effectiveness of the simple indicators described in Section 5 for the detection of malicious Java bytecode.

Setup

Figure 3 shows an overview of the experiment. We select the Top-10 most popular projects from libraries.io, which at the time of writing (July 2022) are: junit, guava, h2database, spring-test, spring-context, spring-core, spring-orm, gson, mockito-core, and lombok.

We artificially created infected versions of the latest version of each project as follows. We convert the three malicious Java code excerpts (payloads) from BKC in bytecode using ASMifier [START_REF]ASMifier (ASM 9.3[END_REF]. We refer to Listing 1 as Payload 1 (P1), Listing 2 as Payload 2 (P2), and Listing 3 as Payload 3 (P3). Then, we extract the JARs of the benign packages, randomly select a class file, add the payload via bytecode injection at the beginning of the first available method in the class, and re-create the archives. Therefore the final set of packages consists of 40 JARs: the 10 Original versions (O) and the 30 versions infected with P1, P2, and P3 respectively.

P1 uses an execution API to run a bash command that decodes a base64 string and executes its content. This payload is placed in a try block associated with an empty catch.

P2 uses reflection to dynamically invoke the content of a malicious class that is hosted and read directly from the internet. This payload does not have an empty catch clause.

P3 downloads a Groovy script, stores it in a local file, and executes its content. Similarly to P1, also P3 is placed in a try block associated with an empty catch clause.

The original JARs and the infected ones are analyzed as described in the following section. The "JAR scanner" component in Figure 3 applies the analyses described in Section 5.

Analysis

We evaluate the capabilities of the indicators of Section 5 and their combination to recognize malicious JARs.

Constant Pool. We evaluate the efficiency of different combinations of filtering methods (cf. Section 5) and Table 4 shows the average results for all the infected packages.

First, we evaluate the removal of strings that are recognized as sentences by the language detector (cf. column LC). Secondly, we evaluate the removal of strings characterized by a Shannon entropy below the third quartile computed in two cases: at JAR and the class level (cf. columns SH 𝐽 and SH 𝐶 , resp.). On the total of 30 infected packages, we observe that filtering at the class level performs better than at the JAR level: SH 𝐽 globally shows lower precision, recall, and accuracy than SH 𝐶 . Finally, we combine SH 𝐶 and LC with two methods for the removal of output messages: the one based on Kullbac-Leibler divergence (using thresholds of 2 and 10) and the other based on language detection. For P1 and P3, the Shannon-based filter at the class level associated with Kullbac-Leibler using a threshold of 10 (cf. column SH 𝐶 +KL 10 ) reduces most strings without removing those belonging to the malicious injection. However, the filter based on relative entropy misses the significant strings of P2 (i.e., the URL). This happens because the probability distribution of an URL containing a domain (e.g., swmail.malware.index) rather than an IP address is comparable with the one of English characters. Therefore, the best trade-off between precision, recall, and accuracy is offered by the Shannon filter at the class level combined with language detection (cf. column SH 𝐶 +LC) and is adopted in the subsequent analysis.

Except for the LC case, which retains 2 of the 3 strings added by P2, the recall value is low for P2 and P3. This is because strings such as addURL (cf. Listing 2) or /tmp/evil.groovy (cf. Listing 3) have a low Shannon entropy and thus are filtered out. Nevertheless, the malicious URLs added by P2 and P3 are always kept allowing the detection of these injections.

Finally, searching for sensitive keywords in different formats (cf. Section 5.2) proves to be an effective technique for detecting malicious strings and further improves the performances of the filters shown in Table 4. For example, SH 𝐶 +LC combined with the search of sensitive keywords keeps unchanged the recall for this filter, reduces the initial number of strings by 99.8%, and improves accuracy (i.e., 99.9% for P1, 66.4% for P2, and 74.8% for P3). Sensitive APIs. In this part of the analysis, we evaluate to what extent the detection of sensitive APIs may be an indicator of malicious JARs. To do so we scan the list of instructions within all the methods of each class file. For each category of API (cf. Section 5.3) we report the signature of the detected API and the names of the class and method containing it.

Figure 4 shows, for instance, the results of the scan for the four versions of mockito-core (i.e., the original and the three infected versions). In total, we detect 68 calls to sensitive APIs in the original version. The version infected with P1 differs from the original one because of the presence of an execution API (i.e., exec from the Runtime library). The version containing P2 shows additional API calls related to networking and dynamic programming, while the P3 version shows additional APIs related to networking and file output. In Fig. 4 the presence of an execution-related API is an outlier compared to the original version. However, execution APIs are legitimately used by other packages we considered (e.g., h2database).

We can conclude that depending on the type of library under consideration, there may be greater or lesser use of APIs related to a specific category. This affects the extent to which the presence of a method call related to a category is discriminant for malicious code detection. Still, in Fig. 4, the API calls used by the infections P2 and P3 could be overlooked among the legitimate calls to APIs of the same categories.

Empty Catch Clauses. In this case, we evaluate how the detection of empty catch clauses (when payloads use such a feature) for the detection of malicious JARs.

For each method contained in a class, we report the name of the class and method that contains the empty catch, and the instructions belonging to the corresponding try block. We also report the detected sensitive APIs and the appearance of suspicious strings from the constant pool. Table 5 reports the average results for all the infected packages. In both cases of P1 and P3 the malicious insertion is detected (P2 is not characterized by an empty catch). Reporting try blocks that contain sensitive APIs (T+API) reduces on average the number of blocks to be reviewed by 86%. Adding the search for suspicious strings (after the SH 𝐶 +LC filter) in the associated try block (T+API+S) reduces the blocks to be reviewed by 97.6% for P1 and 97.4% for P3. For both P1 and P3, the malicious insertion is detected (i.e., recall value of 1.0).

We can conclude that the detection of empty catch clauses coupled with the detection of sensitive APIs and suspicious strings turns out to be a valid approach for the detection of malicious code. The final number of items to be reviewed is small and relevant. Table 5: Average results for the empty-catch analysis. We report the reduction factor (rf), precision (P), and recall (R) of the filters based on considering try blocks containing sensitive API call(s) (T+API) and the further check of suspicious strings (T+API+S). ( * ): analysis not applicable to the P2 case.

Intra-Procedural Data Flow Analysis. As described in Section 5.3, for each of the detected sensitive APIs we perform an intra-procedural data-flow analysis to find their input values. We then check whether they are also among the suspicious strings. The data-flow analysis used is always able to report the type of the input, whereas its value is provided only when the method contains a string. Table 6 reports average results for all infected packages. Considering the cases for which data-flow analysis succeeds in finding the actual value of the input (cf. column DFA), we reduce the results to be inspected by 73.7% for P1, 75.5% for P2, and 73.1% for P3. By comparing the detected input values with the suspicious strings, we further reduce the information to be reviewed for all three infected versions (still containing the malicious additions, as shown by the unchanged recall values). Compared to the empty catch clause analysis, the data-flow analysis reduces less the information but has the benefit of covering also cases where malicious payloads are not associated with empty catch clauses.

Type

LIMITATIONS

The problem of deciding whether a program is malicious is undecidable because of its relation to the Halting problem [START_REF] Filiol | Computer viruses: from theory to applications[END_REF]. For Chess and White's looser detection model thus we have to accept false positives [START_REF] Filiol | Computer viruses: from theory to applications[END_REF]. We evaluate different indicators for the static analysis of Java bytecode to detect malicious code. Therefore our methodology inherits the limitations of static approaches [START_REF] Moser | Limits of Static Analysis for Malware Detection[END_REF]. In addition, our analysis has been based on the malwares falling into the categories described in Section 4.2. Other types of malicious code changes, e.g., insertion of hidden credentials or removal of security checks, are out of our scope. Moreover, in spite of our best effort in building an extensive list of sensitive Java APIs, our approach does not cover attacks carried out using different API calls.

As for data-flow analysis, our approach is limited to cases where the malicious payload and the API using it are in the same method (intra-procedural analysis): more complex cases where the attacker spread different parts of the payload in multiple places are out of our current scope.

Finally, Shannon entropy is low for short strings and for strings with a short alphabet (e.g., binary strings, base16). An attacker could then challenge our detection by breaking the payload into shorter strings or using respective encodings.

CONCLUSION AND FUTURE WORKS

To detect malicious code following attacks on the OSS supply chain in the Java ecosystem, we propose a static analysis of the constant pool and of the JVM bytecode instructions.

For the constant pool, we evaluated different filtering approaches to reduce the number of elements to be reviewed when performing malicious code analysis. We find that a filter based on taking the third quartile at the class level of the Shannon entropy of the strings coupled with language detection is able to reduce the number of false positives, without removing the relevant information. Adding the check for sensitive keywords among the remaining strings further highlights the malicious insertions.

For the bytecode instructions, we detect sensitive API calls within the entire set of instructions and in try blocks associated with empty catch clauses, then we perform intra-procedural analysis on them. Also in this case we reduce the false positives and we capture the malicious additions.

In future works, we aim at improving the data-flow analysis by considering the inter-procedural flows. We also aim at characterizing the Maven Central ecosystem 4 in terms of usage of critical APIs. Due to the scarcity of malware samples in Java, we also plan to evaluate automated classification approaches based on anomaly detection and using the indicators described in this work.

FileOutputStream fs = new FileOutputStream (" / tmp / evil . groovy ") ;

B EXAMPLE OF STRING PRE-PROCESSING

As described in Section 5.2, before performing the language detection we pre-process the string to be analyzed. An example of such pre-processing is provided in Listing 4.

Listing 4: Example of pre-processing of a string before applying the Kullbac-Leibler filter or the language detection as described in Section 5.2 1 s1 = " http :// swmail . malware . index / evilmaven . jar " 2 list1 = word_tokenize ( s1 ) 3 # Output : [" http " , ":" , "// swmail . malware . index / evilmaven . jar "] 4 list1 = remove_symbols_from_words ( list1 ) 5 # Output : [" http " , "" , " swmailmalwareindexevilmavenjar "] 6 s1 = reassemble_words ( list1 ) 7 # Output : " http swmailmalwareindexevilmavenjar " 8 cld2 . detect ( s1 ) 9 # Output : Reliable : False , Details : (' Unknown ', 'un ', 0 , 0.0) 10 11 s2 = " array lengths differed , expected . length = " 12 list2 = word_tokenize ( s2 ) 13 # Output : [" array " , " lengths " , " differed " , " ," , " expected . length ="] 14 list2 = remove_symbols_from_words ( list2 ) 15 # Output : [" array " , " lengths " , " differed " , "" , " expectedlength "]

4 . 6 }

 46 exec (" bash -c { echo , YmFz ** SHORTENED ** JjE =} 5 |{ base64 , -d }|{ bash , -i } ") ;OSS supply chain attacks target open-source components as a means of spreading malware. As Ladisa et al.[START_REF] Ladisa | SoK: Taxonomy of Attacks on Open-Source Software Supply Chains[END_REF] pointed out, there are many possible attack vectors.

Figure 1 :

 1 Figure 1: Indexing mechanism in the constant pool.

Figure 2 :

 2 Figure 2: Description of the static analysis of a JAR for the detection of malicious bytecode.

Figure 3 :

 3 Figure 3: Experiment to assess the analysis of malicious Java bytecode.

Figure 4 :

 4 Figure 4: Detection of sensitive APIs for mockito-core@4.6.1.

  n.a. n.a. 99.97% n.a. n.a. P3 85.7% 0.178 1.0 97.4% .950 1.0

19 } 20 22 }

 192022 17 fs . write ( buffer , 0 , byteread ) ; 18 getShell += new String ( buffer ) ; Object value = shell . evaluate ( getShell ) ; 21 System . out . println ( value . toString () ) ;

Table 2 :

 2 AV scan results for malicious samples, per ecosystem. U: undetected, M: malicious, TU: type unsupported, F: failure, T: timeout.

Table 4 :

 4 Average results of different filtering mechanisms applied to strings in the constant pool. In red are the worse results; in bold are the best ones. PS: number of strings introduced by the malicious payload. For each filtering mechanism we present the precision (P), recall (R), and balanced accuracy (bA). LC: language detection applied to all strings. SH: filter based on Shannon entropy at JAR (SH 𝐽 ) and class (SH 𝐶 ) level. SH+KL: Shannon-based filter combined with Kullbac-Leibler divergence using thresholds of 2 and 10. SH+LC: Shannon-based filter combined with language detection.

			LC			SH 𝐽			SH 𝐶			SH 𝐶 +KL 2		SH 𝐶 +KL 10		SH 𝐶 +LC
	PS	P	R	bA	P	R	bA	P	R	bA	P	R	bA	P	R	bA	P	R	bA
	P1: 1 .003 1.0 .738 .005 1.0 .847 .013 1.0 .933 .239 1.0 .996 .453 1.0 .998 .157	1.0	.989
	P2: 3 .006 .667 .572 .004 .30 .525 .013 .333 .559 0.0 0.0 .498 0.0 0.0 .498 .157 .333 .662
	P3: 2 .006 1.0 .738 .004 0.45 .571 .013	.5	.683 .239 .5 .746 .453 0.5 .749 .157	.5	.739

Table 6 :

 6 Average results for data-flow analysis. We report the reduction factor (rf), precision (P), and recall (R) for the filters for which the data-flow analysis detects the actual input value (DFA) and for those that have input strings that are among the suspicious ones (DFA+S).

			DFA			DFA+S
		rf	P	R	rf	P	R
	P1	73.7% .195 1.0 94.6% .600 1.0
	P2	75.5% .195 .333 94.4% .617 .333
	P3	73.1% .264 1.0 94.7% .617 1.0
	Response to RQ2
	Through the described experiment we assessed how the
	indicators considered in RQ1 perform in the detection of
	malicious Java bytecode.
	Constant Pool: The Shannon entropy values of the strings
	compared at the class level performs better than the ones
	compared at the JAR level since for the latter we observed
	more removals of malicious strings. Language detection
	performs better than relative entropy measurement (with
	English characters), as the latter does not work in cases
	where injected strings are composed of English words.
	Bytecode Instructions: Looking for sensitive APIs and
	suspicious strings in try blocks associated with empty
	catch clauses reduces irrelevant information without re-
	moving malicious additions. Searching for suspicious
	strings among input values to sensitive APIs found by
	data-flow analysis is helpful in detecting malicious behav-
	ior.

Table 7

 7 present the list of sensitive APIs that we have used for scanning OSS packages. Such list comprise only native APIs and has been built starting from real malware examples in the context of OSS supply chain attacks. Then we enriched such a list by including methods with similar functionalities to the initial set of APIs.

https://libraries.io/

https://www.virustotal.com

This section highlights the main observations from the manual inspection of malwares, then presents the indicators for the detection of malicious code at the bytecode level (Figure2).

Acknowledgements. We thank all the reviewers for their feedback. This work is partly funded by EU grants No. 830892 (SPARTA) and No. 952647 (AssureMOSS)

A JAVA MALICIOUS SAMPLES

In this section we report the code snippets of the malicious samples written in Java that are available in the BKC [START_REF]Backstabber's Knife Collection[END_REF]. Throughout the paper we refer to Payload 2 to the code shown in Listing 2 and to Payload 3 to Listing 3.

Listing 2: Malicious code snippet from CompilerMojo.java contained in com.github.codingandcoding:maven-compilerplugin@3.9.0


Piergiorgio Ladisa
email: piergiorgio.ladisa@sap.compiergiorgio.ladisa@irisa.fr

Henrik Plate
email: henrik.plate@sap.com

Matias Martinez
email: matias.martinez@uphf.fr

Olivier Barais
email: olivier.barais@irisa.fr

Serena Elisa Ponta
email: serena.ponta@sap.com

Risk Explorer for Software Supply Chains Understanding the Attack Surface of Open-Source based Software Development

Keywords: Security and privacy → Software security engineering Open-Source Security, Supply Chain Attacks, Malware Detection ACM Reference Format:

Supply chain attacks on open-source projects aim at injecting and spreading malicious code such that it is executed by direct and indirect downstream users. Recent work systematized the knowledge about such attacks and proposed a taxonomy in the form of an attack tree.

We propose a visualization tool called Risk Explorer for Software Supply Chains, which allows inspecting the taxonomy of attack vectors, their descriptions, references to real-world incidents and other literature, as well as information about associated safeguards.

Being open-source itself, the community can easily reference new attacks, accommodate for entirely new attack vectors or reflect the development of new safeguards.

INTRODUCTION

Open-Source Software (OSS) is extensively used across the whole technology stack. At the same time, more and more incidents Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the owner/author(s). shows that attackers discovered open-source projects as a means for spreading malware to downstream users.

Ladisa et al. [2] propose a taxonomy in the form of an attack tree to systematically describe attack vectors at the disposal of attackers, independent of technologies or ecosystems. Each attack vector is supported by scientific works and real-world examples, and linked to existing safeguards (if any).

To facilitate its use, adoption, and extension by the open-source and security communities, we developed and open-sourced an online tool supporting the visualization and exploration of the taxonomy and all the related information [START_REF] Figueiras | Towards the Understanding of Interaction in Information Visualization[END_REF] .

In the remainder of the paper, Section 2 describes the tool implementation and how to contribute, Section 3 outlines possible use-cases, and Section 5 concludes with closing remarks and an outlook.

RISK EXPLORER

Our work proposes a companion tool to the taxonomy of OSS supply chain attacks [2]. Being open-source, it facilitates keeping the said taxonomy relevant and up to date, similarly to other communitydriven efforts, e.g., Common Weakness Enumeration (CWE) [START_REF] Ladisa | SoK: Taxonomy of Attacks on Open-Source Software Supply Chains[END_REF] .

The tool has been developed using React.js3 , a front-end framework for single-page applications, and is hosted by a Node.js server. As such, it can be served via GitHub Pages, and the iterative exploration of the attack tree happens in the browser.

The interactive visualization of the attack tree is the tool's main functionality and has been implemented using the collapsible tree from the d3.js library4 . Users can collapse and expand the different nodes of the attack tree to explore the attack surface of open-sourcebased software development. The description of the respective attack vector, references, as well as associated safeguards are shown below the tree (cf. Figure 1). This exploratory mode of visualization offers to the user the benefit of managing visual complexity and accessing information in more consumable portions on-demand [1]. A share button generates a deep link to individual attack vectors, which can be referenced from 3rd party websites, e.g., in training material or security advisories. A search field in the top-right corner allows searching for attack vectors by name. Upon selection, the respective path from the root node to the selected attack vector is expanded and highlighted in red. The second search field right below is for safeguards. Upon selection, all the nodes mitigated by the respective safeguard are colored in green (cf. Figure 1).

Additionally, all attack vectors, safeguards, and bibliographical references can also be displayed in tabular form on dedicated pages. References can be sorted after title, publication year and affected ecosystem. The tabular display of attack vectors also allows showing information about associated safeguards in a modal window.

USE CASES

The tool can be used to raise awareness among developers and for training purposes. Security advisories could use deep links to reference the attack vector(s) used in a given attack. Another use-case is to support threat modeling activities for development and build environments, both for open-source and proprietary development projects. Similarly to the ATT&CK Navigator 5 , the tool can also be used for red/blue team planning and security assessments. Finally, the visual highlight of attack vectors covered by given safeguards can help in the selection and design of security controls.

The tool is used by a security expert providing guidance on supply chain security across the entire organization. She uses it "to learn about specific software supply chain attacks, [...] its relation in the chain and suggested safeguards". She reported that, through the suggested safeguards and linked references, the tool "helped learning more about preventive and detective measures". Content, but especially the combination of features offered by the tool, e.g. "the visualization and mapping, [and the] ability to see cross-references", was reported as a strength. On the other hand, she pointed out some UI bugs and the need to have "deep knowledge of the topic to understand how to use the safeguards". The expert concluded that she "will continue to reference to this research while improving security practices for development".

HOW TO CONTRIBUTE

The tool and its underlying data are hosted on GitHub 6 . The flat data structures in separate files facilitate the addition and update of information. To this end, the repository also contains a template for references, which is supposedly the most frequent addition, e.g., to reflect new attacks or scientific publications. When Pull Requests are merged, a new version of the page is automatically deployed.

CONCLUSION AND FUTURE WORKS

This paper proposes a visualization tool for the taxonomy in [2]. With new attacks occuring, the evolution of the taxonomy is facilitated by the tool and data being open-source.

In future work, the tool can be extended to hold a more comprehensive database of OSS supply chain incidents. So far, only a subset of affected packages is referenced.

Another possible extension is to reflect the results of automated or manual assessments done for a given development project, to highlight open and covered attack vectors, similar to what the Atomic Red Team tool 7 does for the ATT&CK framework.

Figure 1 :

 1 Figure 1: Screenshot of the attack tree visualization (in green attack vectors covered by safeguard Reproducible builds).

  5 https://mitre-attack.github.io/attack-navigator/

https://sap.github.io/risk-explorer-for-software-supply-chains/

https://cwe.mitre.org

https://reactjs.org/

https://d3js.org/

Acknowledgements. We thank all the reviewers and the security practitioner for their feedback. This work is partly funded by EU grants No. 830892 (SPARTA) and No. 952647 (AssureMOSS)


Quentin Voortman
email: q.j.t.voortman@tue.nl

Denis Efimov
email: denis.efimov@inria.fr

Alexander Yu Pogromsky
email: a.pogromski@tue.nl

Jean-Pierre Richard
email: jean-pierre.richard@centralelille.fr

Henk Nijmeijer
email: h.nijmeijer@tue.nl

An event-triggered observation scheme for systems with perturbations and data rate constraints ✩

Keywords:

In this paper, an event-triggered observation scheme is considered for a perturbed nonlinear dynamical system connected to a remote location via a communication channel, which can only transmit a limited amount of data per unit of time. The dynamical system, which is supposed to be globally Lipschitz, is subject to bounded state perturbations. Moreover, at the system's location, the output is measured with some bounded errors. The objective is to calculate estimates of the state at the remote location in real-time with maximum given error, whilst using the communication channel as little as possible. An event-triggered communication strategy is proposed in order to reduce the average number of communications. An important feature of this strategy is to provide an estimation of the relation between the observation error and the communication rate. The observation scheme's efficiency is demonstrated through simulations of unicycle-type robots.

Introduction

Efficiency has always played a central role in the field of system dynamics and control. In the past twenty years, with the appearance of wireless technologies, efficiency has gained a new meaning. It is not enough to simply observe and control systems. These tasks should in addition be carried out in a way that is efficient in terms of data rates. This quest for efficiency has lead to the birth of an entire sub-field: control and estimation over data rate constrained communication channels [START_REF] Matveev | Estimation and control over communication networks[END_REF][START_REF] Yüksel | Stochastic networked control systems[END_REF]. The problems in this sub-field share some common ingredients: one or several dynamical systems, communication channels, or other devices such as controllers, actuators, sensors, that interact by exchanging messages in the presence of a source of uncertainty. This uncertainty can be in ✩ It was elaborated in the UCoCoS project which has received funding from the European Union's Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 675080. The 21st IFAC World Congress (IFAC 2020), July 12-17, 2020, Berlin, Germany. This paper was recommended for publication in revised form by Associate Editor Hernan Haimovich under the direction of Editor Sophie Tarbouriech. the form of noise, perturbations, parametric uncertainty, or deviations in the initial conditions. The incertitude can be understood as information in the sense of Shannon's theory (see [START_REF] Shannon | A mathematical theory of communication[END_REF]). This information needs to be transmitted via the communication channels, which are generally limited either in the frequency at which they can send messages or in the number of bits they can transmit per unit of time and can be subject to losses or noise themselves.

The earliest work in this sub-field focused on linear systems. For example, these early results include [START_REF] Wong | Systems with finite communication bandwidth constraints -Part I: State estimation problems[END_REF], where the problem of state estimation for a stochastic plant over data rate constrained communication is investigated, and [START_REF] Elia | Stabilization of linear systems with limited information[END_REF], where the problem of stabilization of a linear plant with limited communication is considered. Many more results were obtained for linear systems and broad surveys of these results are available in [START_REF] Nair | Feedback control under data rate constraints: An overview[END_REF], [START_REF] Baillieul | Control and communication challenges in networked real-time systems[END_REF] and [START_REF] Andrievsky | Control and estimation under information constraints: Toward a unified theory of control, computation and communications[END_REF]. For nonlinear systems, results followed soon after. These include De [START_REF] Persis | A note on stabilization via communication channel in the presence of input constraints[END_REF], where the problem of the stabilization of a nonlinear system via a constrained channel is posed, and [START_REF] Baillieul | Data-rate requirements for nonlinear feedback control[END_REF] which investigates the data rate requirements for feedback control. Both of these early works assumed a particular structure on the nonlinear system. Results for more general structures were obtained in [START_REF] Nair | Topological feedback entropy and nonlinear stabilization[END_REF] and [START_REF] Liberzon | Stabilization of nonlinear systems with limited information feedback[END_REF] which adapted techniques for linear systems from [START_REF] Nair | Exponential stabilisability of multidimensional linear systems with finite data rates[END_REF] and [START_REF] Liberzon | Hybrid feedback stabilization of systems with quantized signals[END_REF] to nonlinear ones. We put the emphasis on [START_REF] Nair | Topological feedback entropy and nonlinear stabilization[END_REF] because it is among the first papers to introduce a notion of entropy (in this case, topological feedback entropy) to describe the minimum sufficient data rate to stabilize a system. Several other notions of entropy have since been used to provide bounds on the sufficient and/or necessary data rates allowing for constrained control and/or observation of unperturbed systems. These results include invariance entropy [START_REF] Kawan | Invariance entropy for deterministic control systems an introduction[END_REF], feedback entropy, [START_REF] Colonius | A note on topological feedback entropy and invariance entropy[END_REF] topological entropy [START_REF] Liberzon | Entropy and minimal data rates for state estimation and model detection[END_REF][START_REF] Matveev | Observation of nonlinear systems via finite capacity channels: Constructive data rate limits[END_REF][START_REF] Matveev | Estimation and control over communication networks[END_REF][START_REF] Savkin | Analysis and synthesis of networked control systems: Topological entropy, observability, robustness and optimal control[END_REF][START_REF] Sibai | State estimation of dynamical systems with unknown inputs: Entropy and bit rates[END_REF][START_REF] Voortman | Data-rate constrained observers of nonlinear systems[END_REF], estimation entropy/α-entropy [START_REF] Kawan | Exponential state estimation[END_REF][START_REF] Sibai | Optimal data rate for state estimation of switched nonlinear systems[END_REF], and restoration entropy (Matveev & Pogromsky, 2019). As an alternative to notions of entropy, some works such as [START_REF] Fradkov | Passification based synchronization of nonlinear systems under communication constraints and bounded disturbances[END_REF], [START_REF] Fradkov | Synchronization of nonlinear systems under information constraints[END_REF] relied on passivity-based methods to provide bitrate bounds. The aforementioned results on entropy are limited to unperturbed systems as the entropy of a perturbed system is, generally speaking, infinite (see [START_REF] Matveev | Estimation and control over communication networks[END_REF]) and, as such, entropy is not a useful mathematical tool to analyze uncertain systems.

For similar reasons, another topic: event-based control. Some of the earliest works include (Åarzén, 1999), where an eventtriggered PID controller is presented and [START_REF] Åström | Comparison of periodic and event based sampling for first-order stochastic systems[END_REF], where the effects of event-based sampling are compared to periodic ones. An introduction to event-based control can be found in [START_REF] Heemels | An introduction to event-triggered and self-triggered control[END_REF] and an overview of sampling-related results in [START_REF] Hetel | Recent developments on the stability of systems with aperiodic sampling : An overview[END_REF] and [START_REF] Ge | Distributed event-triggered estimation over sensor networks: A survey[END_REF].

One possible approach to obtain constructive bounds for sampled-data systems relies on LMI-based techniques. Early results include [START_REF] Fridman | Robust sampled-data stabilization of linear systems: An input delay approach[END_REF] which provides sufficient conditions for the robust sampled-data stabilization of linear systems with delayed input and [START_REF] Fu | The sector bound approach to quantized[END_REF] which considers several quantized feedback designs for linear systems. Recently, LMI-based techniques have been employed for nonlinear systems with specific structures such as Lur'e-type systems [START_REF] Seifullaev | Event-triggered control of sampled-data nonlinear systems[END_REF][START_REF] Zhang | Absolute stabilization of Lur'e systems under event-triggered feedback[END_REF], nonlinear systems with cone-bounded nonlinearities [START_REF] Tarbouriech | Observer-based event-triggered control for linear systems subject to cone-bounded nonlinearities[END_REF] and with cone-bounded nonlinear inputs [START_REF] Moreira | Observer-based event-triggered control in the presence of cone-bounded nonlinear inputs[END_REF].

In some recent works, both concepts (data rate constraints and event-based) have explicitly been used together for control and observation purposes. Among them are [START_REF] Han | Stochastic event-triggered sensor schedule for remote state estimation[END_REF], which uses an event-triggered sensor schedule for remote estimation for a linear system, [START_REF] Shi | Event-based state estimation of linear dynamic systems with unknown exogenous inputs[END_REF], designing a remote estimator for a linear system with unknown exogenous inputs, [START_REF] Huang | Event-triggered state estimation with an energy harvesting sensor[END_REF], where a remote estimator for a system with an energy harvesting sensor is developed, [START_REF] Trimpe | Event-based state estimation: An emulationbased approach[END_REF], which tackles distributed state estimation with data rate constraints, [START_REF] Xia | Networked state estimation over a shared communication medium[END_REF], which considers networked state estimation with a shared communication medium and, [START_REF] Mosek Aps | Distributed event-based state estimation for networked systems: An LMI approach[END_REF], where an LMI approach is used.

Focusing on the observation, the problem statement in this paper is motivated by the following practical situation: a unicycletype robot needs to communicate its position and orientation to a remote location by using Wi-Fi, whilst measuring only its position and using limited computation capacities. Because wireless networks cannot transmit infinite amounts of data, it is necessary to develop an observation scheme that minimizes the data rate usage. The simplest equations describing a unicycle-type robot are

ẋ1 (t) = v l (1 + d1 (t)) cos(x 3 (t)), ẋ2 (t) = v l (1 + d1 (t)) sin(x 3 (t)), ẋ3 (t) = v θ (1 + d2 (t)), y(t) = [ x 1 (t) x 2 (t) ] + [ w1 (t) w2 (t) ] , (1)
with x(t) = [x 1 (t) x 1 (t) x 3 (t)] ⊺ the state-space vector, y(t) the measured output, where x 1 (t) ∈ R, x 2 (t) ∈ R are the coordinates of the robot in the xy-plane, x 3 (t) ∈ [0, 2π ) is the angular orientation of the robot, v l and v θ are linear and angular velocities respectively, d1 (t) and d2 (t) are perturbations such that dmax ≥ di (t) ≥ dmin > -1 which correspond to an actuation mismatch, and w(t) ∈ R 2 is a measurement error. Note that the bound dmin > -1 implies that the actual velocity v l (1 + d1 (t)) has the same sign as v l , which is a natural condition stemming from experiments (see Guerra, Efimov, Zheng, andPerruquetti (2014, 2017) for more details about this formulation).

In this paper, an event-triggered scheme is developed for the remote observation of systems with Lipschitz nonlinearities, state perturbations, and measurement noise (as in ( 1)) via lossless data rate constrained communication channels. A first important feature of the scheme is that the minimum duration between two consecutive messages that are sent via the channel can be chosen.

A second important feature is that the precision of the estimates can be tuned. Additionally, the observation scheme functions on an event-triggered basis, communicating a new estimate when the precision of the current estimate is not sufficient anymore. The combination of these features leads to an observation scheme that is very efficient in terms of the transmitted number of bits. Providing analytical bounds on the sufficient transmission capacity is the main contribution of this paper. This paper is a generalization and extension of [START_REF] Voortman | Event-triggered data-efficient observers of perturbed systems[END_REF]: a generalization because nonlinear systems are considered, as opposed to linear systems, and an extension because the results are developed for continuous-time systems as opposed to [START_REF] Voortman | Event-triggered data-efficient observers of perturbed systems[END_REF] which considered discrete-time systems. An observer specific for unicycle robots utilizing a similar communication protocol as this paper has been experimentally validated on Turtlebots and the results have been accepted for publication in [START_REF] Voortman | Observing mobile robots with data-rate constraints : A case study[END_REF].

The structure of this work is as follows. First, in Section 2 we specify the problem statement. An observation scheme is developed in Section 3. In Section 4, two results about this observation scheme are exposed. The first one provides a bound on the maximum observation error. The second one evaluates a bound on the so-called ''channel transmission capacity'' which is sufficient to implement the observation scheme. Finally, in Section 5 simulations of the observation scheme are provided for the motivating example (1). These simulations illustrate why the observation scheme is particularly efficient and how its different parameters can be tuned to fit the user's preferences in terms of performance.

Problem statement

We consider continuous-time systems of the following form

ẋ(t) = Ax(t) + Sϕ(Hx(t)) + d(t), y(t) = Cx(t) + w(t), (2) where x(t) ∈ R n is the state, A ∈ R n×n , S ∈ R n×p , ϕ : R p → R p is a vector field, H ∈ R p×n , d(t) ∈ R n is an unknown state perturbation, y(t) ∈ R m is the output, C ∈ R m×n ,
and w(t) ∈ R m is a measurement error. We make the following assumptions about the external signals:

Assumption 1. We have ∥d(t)∥ 2 ≤ δ and ∥w(t)∥ 2 ≤ ω, ∀t ≥ 0, where ∥ • ∥ 2 is the Euclidean norm, δ is the maximum state perturbation, and ω is the maximum measurement error.

We make the following regularity assumption about the righthand side of (2).

Assumption 2. ϕ is Lipschitz with constant L.

Note that the previous assumption can be relaxed to local Lipschitz continuity if the perturbations from Assumption 1 are such that the solutions of (2) are uniformly ultimately bounded [START_REF] Khalil | Nonlinear systems[END_REF]. The system is equipped with a smart sensor (a sensor admitting some computational capacities, which allows it to perform additional computations on the measured data) and it is connected to a remote location via a data rate constrained communication channel, which can only send messages that are of finite size. For any time interval t between two consecutive transmission, the channel can transmit at most b + ( t) bits. The objective is to provide estimates x(t) of x(t) at the remote location by sending messages over this communication channel. The sensor and the remote location are aware of an initial estimate

x(0) which verifies   x(0) -x(0)   2 ≤ ϵ 0 , (3)
where ϵ 0 is a user-specified parameter corresponding to the error of initial conditions. The reason why (3) is assumed, will be discussed further in this paper in Remark 2.

In order to generate the estimates, messages m(t j ), where t j are the transmission times, are sent. Four ingredients interact with these messages: a sampler S , a coder C , an alphabet function A , and a decoder D. The four devices together form a communication protocol. The following constants/parameters are known by all devices: the system matrices A and C , the vector field ϕ, the maximum state perturbation δ, the maximum measurement error ω, the discretization error ϵ (which is induced by coding/decoding operation), and the initial estimate x(0) with its accuracy ϵ 0 .

At the system side, the sampler S generates the instants of transmission in the following way t j+1 = S (t j , {y(s)} t j ≥s≥0 , m(t 1 ), . . . , m(t j )), (4) t 0 = 0. The coder then generates the messages: m(t j ) = C (x(0), {y(s)} t j ≥s≥0 , m(t 1 ), . . . , m(t j-1 )),

(5) ∀t j : j > 0. At each communication instant, the messages are encoded into a finite-sized alphabet (the finiteness being due to the data rate constraints). The alphabet function A determines the last index l j of the messages:

l j = A (x(0), m(t 1 ), . . . , m(t j-1 )), ∀t j : j > 0. (6)
The restriction on the choice of messages is then m(t j ) ∈ {1, . . . , l j }, ∀t j : j > 0. After encoding the messages, the number of transmitted bits should not exceed the maximum number of bits that can be sent during the communication. This implies the following constraint on the alphabet length:

log 2 l j ≤ b + (t j+1 -t j )∀t j : j > 0. (7)
At the remote location, the decoder D receives the messages and interprets them to generate a deterministic estimate of the state x(t) in the following way

x(t) = D(x(0), m(t 1 ), . . . , m(t j )), ∀t ∈ [t j , t j+1 ), (8)
∀j ≥ 0. Because of the perturbation, measurement error and finite data rate, it is impossible to provide exact estimates at the remote location.

Definition 1. Let ( 2) and ( 8) define respectively the state and its estimate. Then, the quantity ξ :

= sup t≥0   x(t) -x(t)  
2 is called the maximum observation error. The goals of the paper are:

(1) To design the observation scheme (4), ( 5), ( 6), and ( 8) such that ξ < ∞.

(2) To guarantee that its performance in terms of data rate is better when the perturbations are not the worst-case realizations.

(3) To investigate the relationship of the time interval between subsequent communications tj := t j+1 -t j , the maximum number of bits per time interval b + (•), and ξ for the proposed communication scheme.

Designing the devices

In this section, we introduce the different devices of the communication protocol. The main mechanism can be described as follows: the sensor emulates the dynamics of the remote estimate on the last sent estimate and forwards a new local estimate whenever such value is ''far away'' from the ''true" local measurement. More specifically, at the sensor side, a local observer transforms the output into estimates of the state x(t). A copy of the decoder is also simulated by the computational capacity of the sensor so that the sensor knows the current estimate x(t) the decoder currently has. This 'copy' of the remote estimate which is provided by the smart sensor will be denoted xc (t). Starting at the initial estimate x(0) and in the absence of messages, the decoder computes real-time estimates as solutions of (2) without perturbations. When the distance between x(t) and xc (t) = x(t) becomes larger than the prescribed maximum error (including a margin for the local observation error ē(t) := x(t) -x(t)), the sampler decides to communicate and the coder sends a message to the decoder to provide a new estimate x(t). Fig. 1 depicts how the different elements interact. Below, each of these algorithms is presented in detail.

The local observer

The local estimate x(t) has the following dynamics

ẋ(t) = Ax(t) + Sϕ(H x(t)) + K (y(t) -C x(t)), (9)
where K ∈ R n×m is a gain matrix. The dynamics of ē(t) are

ė(t) =(A + KC )ē(t) + S(ϕ(Hx(t)) -ϕ(H x(t))) + d(t) + K w(t). ( 10
)
The local observer uses x(0) = x(0) as an initial point, which implies that ∥ē(0)∥ ≤ ϵ 0 . The gain K is computed by using the solutions of the LMI program: arg min

M,P,Y ,γ i -γ 1 + δ 2 γ 2 + ω 2 γ 3 , s.t. ⎡ ⎢ ⎢ ⎣ Q 11 PS P Y S ⊺ P -S ⊺ MS 0 p×n 0 p×m P 0 n×p -γ 2 I n 0 n×m Y ⊺ 0 m×p 0 m×n -γ 3 I m ⎤ ⎥ ⎥ ⎦ ⪯ 0, P ≻ 0, M ≻ 0, γ 4 I p ⪰ S ⊺ MS, γ 1 > 0, γ 2 , γ 3 , γ 4 ≥ 0, (11)
with

Q 11 = A ⊺ P + C ⊺ Y ⊺ + PA + YC + γ 1 I n + γ 4 L 2 H ⊺ H,
∥ē(t)∥ 2 ≤ η, ∀t ≥ 0. ( 12
)
The proof of this proposition is provided in Appendix A.

Remark 1. The objective function of the LMI (11) simply aims to minimize the size of the attractive region (by maximizing γ * 1 and minimizing γ * 2 and γ *

3 ). This, in turn, minimizes the bound on the local observation error. Ideally, one would want to minimize η but this leads to a -generally intractable -nonlinear matrix inequality problem.

The protocol description

We now present the communication procedure, which we will further reference as Procedure 1. It is composed of a sampler, alphabet function, coder, and decoder as described below. For this particular communication procedure, a minimum time interval between communications is going to be employed. This quantity, denoted as t, is known by all devices. It is a user-specified parameter, which is to be chosen finite and it directly influences the upper bound on the estimation error. To properly describe the communication instants, we will need several quantities. The indexes j of the communication instants are inherently known by all devices. The quantity ¯j(t) refers to the index of the last instant of communication (initially, j(0) = 0). This quantity is always known by the sampler (because it knows how many communication instants it defined), the coder (because it knows how many messages it sent), as well as the decoder (because it knows how many messages it received). In between messages (i.e. for t ∈ [t j , t j+1 )), estimates x(t) and xc (t) are computed as

ẋ(t) = Ax(t) + Sϕ(H x(t)), (13)
with the initial conditions x(t j ) coming from the messages m(t j ).

Before we can define the communication protocol, an extra lemma is necessary. The alphabet relies on the assumption that the estimate x(t) will lie within a known set V j when the communications occur. This assumption guarantees that

  x(t) -x(t)   2 ≤ ϵ
after each communication instant, which makes the procedure repeatable:

Lemma 1. For any t j ≥ 0, x(t j ), x(t j ) ∈ R n , ϵ > 0, η > 0 such that   x(t j ) -x(t j )   2 ≤ ϵ + η, and t > 0, the following holds   x(t) -x(t)   2 ≤ e µ * 1 t 2 (ϵ + η) + δ √ µ * 2 √ e µ * 1 t -1 µ * 1 , ( 14
)
∀t ∈ [t j , t j + t], where x(t) is the solution of (2) with x(t j ) as an initial condition, x(t) is the solution of (13) with x(t j ) as an initial condition and

(µ * 1 , µ * 2 , M * ) := arg min µ i , M µ 1 + δ 2 µ 2 , s. t. ⎡ ⎢ ⎣ A ⊺ + A -µ 1 I n + L 2 µ 3 H ⊺ H I n I n I n -µ 2 I n 0 n×n I n 0 n×n -S ⊺ MS ⎤ ⎥ ⎦ ⪯ 0, µ 3 I p ≥ S ⊺ MS, µ i ≥ 0. ( 15
)
The proof of this lemma is provided in Appendix B. Note that ( 15) is an LMI program. Because of its formulation, (15) always admits a solution (this can be seen from the fact that µ i can be chosen arbitrarily large, which makes the first inequality to hold for some µ i sufficiently large).

Procedure 1. The Sampler: For all t ≥ t¯j (t) + t, the sampler verifies whether the following condition is satisfied

  x(t) -xc (t)   ≤ e µ * 1 t 2 (ϵ + η) + δ √ µ * 2 √ e µ * 1 t -1 µ * 1 -η, ( 16
)
where µ * 1 and µ * 2 are solutions of (15). If the condition is not met, a message must be sent to provide a new estimate. The sampler thus updates ¯j(t) and t¯j (t) = t (j increases by one and ¯j(t) = j).

The Alphabet Function: If t = t¯j (t) , the coder and decoder build a covering of the set V j , where V j is defined as

V j := ⎧ ⎨ ⎩ x ∈ R n ⏐ ⏐ ⏐ ⏐ ⏐ ⏐   x-x(t j )   2 ≤ e µ * 1 t 2 (ϵ + η) + δ √ µ * 2 √ e µ * 1 t -1 µ * 1 ⎫ ⎬ ⎭ , ( 17
)
with balls of size ϵ. The balls in the covering are numbered from 1 till l¯j (t) , where l¯j (t) is the length of the alphabet and hence the output of the alphabet function.

The Coder: At the communication instants, the coder function finds the index of the ball in the covering whose center is the closest to x(t j ) and sends this index over the channel. To get x c (t), the coder computes the solutions of (13) with the center of that ball as an initial condition.

The Decoder: When the decoder receives a message, it computes the solutions of (13) with the center of that ball as an initial condition. This solution is then used as x(t).

The strategy to build the alphabet is based on the following idea. As was previously mentioned, in the absence of messages, new estimates are obtained by computing the solutions of (13). After receiving a message, the state of the system x(t) is contained in a ball of a certain radius whose center is the estimate x(t). In the absence of any messages, this ''ball'' of uncertainty is gradually deformed into a larger/small uncertain set. The uncertain set evolves due to three factors: first of all, the unknown state perturbation d(t) increases its radius, secondly, the uncertainty set is stretched/compressed by the action of the dynamics of the system (the deformations are proportional to the eigenvalues A), and thirdly, its radius is increased due to the measurement noise. Given that the communication intervals are chosen to be finite, this uncertain set remains of finite size, estimated by Lemma 1 with t = t, in between communications. It can thus be covered by a finite number of balls of size ϵ > 0. The balls in the covering can be indexed from 1 till l max < ∞. In order to produce such a covering, the only information needed is the initial ball and the different upper bounds on the uncertainties/errors, which implies that both the coder and the decoder can build the set. In order to transmit a new estimate, one can simply send the index of one of the balls whose center then serves as a new estimate with a precision that will depend on ϵ. The cost of communicating in that fashion is dependent on how many balls of size ϵ are required to cover the uncertain set.

Remark 2.

• The coordinates of the centers of the balls used in the covering are always relative to the previous estimate. By communicating in a relative fashion, it is possible to keep the size of the messages limited even if the system is unstable. If the system is unstable, state-space trajectories can drift arbitrarily far away from the origin, which implies that sending an estimate in an absolute fashion (that is, in a coordinate system that is with respect to a fixed point, e.g., the origin), requires to cover all of R n , which needs infinitely many balls and hence infinitely many bits to be sent. The main drawback of communicating in this fashion is that the channel has to be lossless since the loss of a single message would put the communication protocol to a halt. It is possible to make the communication protocol robust towards losses in the communication channel (see e.g. [START_REF] Voortman | Data-rate constrained observers of nonlinear systems[END_REF] for more information on communication protocols that are robust towards losses). This option was not explored as robustness towards losses lies outside of the scope of the current work.

• Since xc (t) = x(t), both devices can build the set I j according to its definition (17). The covering procedure which determines the alphabet is not demanding from a computational point of view since it consists of covering a set that always has the same shape except the whole set is shifted by a certain vector from the origin. Moreover, since this set is centered around the previous estimate, both the coder and decoder can build a covering for it and thus have access to the alphabet.

• The existence of t, the minimum time interval between two consecutive communications, implies that Zeno behavior is automatically avoided since at least t time has to elapse between two triggering instants and t is a strictly positive parameter that does not change during the execution of the communication protocol.

• The assumption that (3) holds is made in order to avoid unnecessarily complicating the communication protocol. If (3) does not hold, then an additional initialization step would be required, during which an initial estimate is provided. Because this step does not change the rest of the communication protocol and would have little impact on the overall communication rate, it is omitted and replaced by the assumption that (3) holds, to facilitate the understandability of the procedure.

Rate and errors

With the observation scheme and its devices fully introduced, we now focus on determining what minimum number of bits per time interval is sufficient to implement the observation scheme. The first result we present provides a closed-form expression for maximum observation error ξ . Proposition 2. The observation scheme described in Procedure 1

ensures that ξ ≤ e µ * 1 t 2 (ϵ+η)+δ √ µ * 2 √ e µ * 1 t -1 µ * 1 for ξ from Definition 1. Proof. At the times of communication,   x(t) -x(t)   2 is at most ϵ, since x(t)
is the center of a ball that contains x(t). From Proposition 1, we have that ∥x(t) -x(t)∥ 2 ≤ η. At the times of communication, we consequently have that

  x(t) -x(t)   2 ≤ η + ϵ. We thus apply Lemma 1, to obtain that following a communication,   x(t + s) -x(t + s)   2 ≤ e µ * 1 t 2 (ϵ + η) + δ √ µ * 2 √ e µ * 1 t -1 µ * 1 ( 18
)
for s ∈ [0, t]. Since after t, the sampler checks whether the distance is going to be exceeded, and a communication resets the distance to ϵ + η should this bound be reached, then (18) holds ∀t ≥ 0.

■

The next result of this section, which is also the main result of the paper, aims to provide a lower bound on b + (•) for the designed communication scheme. In the following theorem, the notation ⌈•⌉ refers to the ceiling function (aka the smallest integer that is greater than the argument of the function).

Theorem 1. The observation scheme described in Procedure 1 with

t > 0 is implementable on any channel with b + ( t) ≥ n log 2 ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ √ n e µ * 1 t 2 (ϵ + η) + δ √ µ * 2 √ e µ * 1 t -1 µ * 1 ϵ ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ . ( 19
)
Proof. In order to implement Procedure 1, ( 7) should be verified for all j. The size of the alphabet is equal to the number of balls of radius ϵ required to cover V j . Since the radius of the set is

e µ * 1 t 2 (ϵ+η)+δ √ µ * 2 √ e µ * 1 t -1 µ * 1
, it can evidently be covered by no more than

⎡ ⎢ ⎢ ⎢ ⎢ e µ * 1 t 2 (ϵ+η)+δ √ µ * 2 √ e µ * 1 t -1 µ * 1 ϵ √ n ⎤ ⎥ ⎥ ⎥ ⎥ n hypercubes of radius ϵ √ n .
These hypercubes are themselves contained in a sphere of radius ϵ. In order to verify ( 7), it thus suffices to take the log 2 of this last quantity, which leads to ( 19) and completes the proof.

Remark 3. As it will be demonstrated in the simulations section, both error bounds presented in this section may be conservative. This is due to several factors:

(1) In the LMI formulation, the Lipschitz nonlinearity is modeled as a perturbation (that has to be compensated). For systems where the Lipschitz nonlinear term plays the most important part in the dynamics, this can be a source of conservatism.

(2) The proof relies on a Lyapunov-like function. As is always the case with Lyapunov functions, better functions can lead to tighter error bounds.

(3) The objective function of ( 11) is suboptimal in the sense that it is a linear formulation that minimizes the size of the convergence region, which depends on a quotient of γ i 's, which is an inherently nonlinear function.

(4) The covering of the set I j is simple but not optimal. A better covering would result in fewer balls being necessary and would improve the bound of Theorem 1.

Regarding point (3) of the above remark, one could alternatively take the objective function γ -1 1 + δ 2 γ 2 + ω 2 γ 3 and use Schur's lemma to transform (11) into an LMI again (this approach is used in e.g. [START_REF] Moreira | Observer-based event-triggered control in the presence of cone-bounded nonlinear inputs[END_REF]). After trying both objective functions out on the simulations which will be presented in the next section, the authors notice no improvement compared with the previous objective function. This different formulation thus was not used.

Case study

In this section, we apply the previously developed observation scheme to the motivating example that was presented in the introduction: a unicycle-type robot with data rate constraints. The goals of this section are:

• To illustrate the validity of the theoretical upper bound ( 19), but also to show that, in a real situation, our observation strategy can be much more efficient;

• To illustrate how the choices of ϵ and t affect the number of communications;

• To show that with an improved local observer, the performance of the scheme becomes much better.

The unicycle-type model that we consider is of the form (1) with

v l = 0.15,   [ d1 (t) d2 (t)] ⊺   2 ≤ 0.1, ∥[ w1 (t) w2 (t)] ⊺ ∥ 2 ≤ 0.
05, and v θ = 0.2. We rewrite this system such that it fits in the form (2) with

A = ⎡ ⎣ 0 0 0 0 0 v l 0 0 0 ⎤ ⎦ , S = ⎡ ⎣ 1 0 0 0 1 0 0 0 1 ⎤ ⎦ , C = [ 1 0 0 0 1 0 ] , H = ⎡ ⎣ 0 0 1 0 0 0 0 0 0 ⎤ ⎦ , ϕ : ⎡ ⎣ r 1 r 2 r 3 ⎤ ⎦ → ⎡ ⎣ v l cos(r 1 ) v l sin(r 1 ) -v l v θ ⎤ ⎦ , d(t) = ⎡ ⎣ v l d 1 (t) cos(x 3 (t)) v l d 1 (t) sin(x 3 (t)) v θ d 2 (t) ⎤ ⎦ .
Assumption 1 holds with δ = 0.1, v l = 0.015 and ω = 0.05. In general, Assumption 2 holds with L = 2v l . However, ( 11) is not feasible with L = 2v l . We can adapt the formulation and solve this issue by using the fact that if the observation error is small, the Lipschitz constant is smaller than 2v l (for ∥x(t) -x(t)∥ 2 ≤ 1, L ≈ v l ∥x(t) -x(t)∥ 2 ). In order to solve the LMI, we thus follow the following steps:

(1) Pose L = L, where L is some arbitrary initial value to be used in solving of the LMI (11);

(2) Compute γ i and K by solving the LMI ( 11) with L = L;

(3) Compute η from Eq. ( 12) and find Lipschitz constant L over the interval [-η, η];

(4) If the Lipschitz constant that we compute is smaller than L, the problem is feasible, if not, we adapt L to a different value and start at step (1) again.

We begin by computing the gain of the local observer K by solving the LMI program (11). Following the aforementioned steps, we pose L = L = 0.38 and obtain K =

[ -0.2447 0 0 -1.2581 0 -1.8184 ] .
To solve the LMI, the MATLAB package YALMIP [START_REF] Lofberg | YALMIP : A toolbox for modeling and optimization in MATLAB[END_REF] was used, together with the MOSEK solver [START_REF] Mosek Aps | Distributed event-based state estimation for networked systems: An LMI approach[END_REF].

With these values, we have η = 0.370964 and for that range, the Lipschitz constant of the system over [-0.370964, 0.370964] is smaller than 0.38. The value for L is thus validated. We then used a Monte Carlo method with 10000 different simulations of the communication scheme from t = 0 till t = 100 with initial conditions (0, 0, 0), an initial estimate randomly chosen in a ball of radius η centered around the origin, and random perturbations.

In order to compare the actual number of transmitted bits with the theoretical maximum number of bits and to show the influence of the choices of ϵ and t, we run several simulations. First, we set t = 0.1 and simulate for various choices of ϵ. In Table 1, we expose the results of the experiments in term of maximum observation error ξ , number of communications N com and number of bits per communication N bits . We make several observations (1) The minimum time interval between two communications is set to 0.1, which implies that we could theoretically communicate 1000 times in 100 s. Clearly, the actual number of communications is much lower than that since it reaches 14.39 when the most precise estimates are sent. In that case, 8 bits need to be sent every time we communicate, on average every 7 s. This shows that the scheme is much more efficient in terms of the actual number of transmitted bits per unit of time, compared to the theoretical sufficient maximum number of bits.

(2) As the precision of the estimates increases, the total error decreases, but the number of transmitted bits increases (more balls are required to cover V j ). There is thus a tradeoff between precision and the number of transmitted bits.

Since ξ is smaller, we also communicate more often.

(3) Decreasing ϵ can only affect the precision up to a certain limit, which is largely dictated by the precision local observer. Since the bound on the local observation error is η = 0.370964, it is impossible to reach this bound for ξ . Moreover, even approaching this bound requires us to decreases ϵ drastically.

For the next set of simulations, we use only one value of ϵ = 0.05 and simulate the observation scheme for various choices of t. The results are displayed in Table 2. We make the following observations about the results:

(1) Increasing t also increases ξ , which is logical: communicating more often leads to better precision.

(2) As t increases, the average time between two consecutive communications drastically increases as well. Even with t = 0.5, we communicate on average less than once every 100 time instants. This is mostly due to the fact that the state perturbations and measurement noise are relatively low.

(3) For almost all choices of t, the number of bits that need to be transmitted is the same. This is due to the fact that the number of bits is rounded upwards. The unrounded number of bits does increase as t increases.

(4) The limiting effect of the local observation error is again present. Even choosing t = 0.01, which corresponds to a sampling of 10 ms, ξ remains large.

In both sets of simulations, the main limiting factor is that the local observer has a limited precision (η = 0.371) and this greatly influences the total error. By using a better local observer (e.g., a nonlinear observer specifically designed for unicycle-type robots), the performance of the observation scheme would be improved. In order to illustrate this fact, we consider the situation where all states of the unicycle robot are observed locally and a local observer is not necessary. We thus consider the same system as the previous example except C = I 3 (where I n is the n×n identity matrix) v l = 0.1, v θ = 0.2, δ = 0.099 and ω = 0.05. This value for δ implies that very large perturbations are possible in the state. In particular, the linear velocity of the robot ranges from 0.001 m/s to 0.199 m/s. Since all states are observed, η = ω = 0.05. We again used a Monte-Carlo method with 1000 different simulations for 100 s.

Fig. 2 shows how the actual observation error evolves over time, together with ∥x(t)-x(t)∥ 2 , which is used for the triggering condition. Note that the distance between both horizontal lines is equal to ω = 0.1. We observe that communication is triggered each time the triggering condition is met. The observation error always remains below ξ . There is some conservatism in the triggering condition, the reasons for which have been discussed in Remark 3. Towards the end, it can be seen that the actual observation error is larger than ∥x(t) -x(t)∥ 2 and the triggering condition, which is due to the measurement noise, and also proves that the protocol is not too conservative.

Fig. 3 shows the trajectory of the unicycle robot in the x 1 -x 2 plane for one particular simulation with ϵ = 0.01 and t = 0.5. We can see that the observation scheme follows the actual trajectory of the system but, due to the state perturbations and the measurement noise, the observation scheme regularly resets to a point close to the current local estimate. The full results of the Monte-Carlo simulations for relevant pairs of ϵ and δ are displayed in Table 3. We make the following observations about these results. (1) Although large state perturbations are present, the observation scheme is still more efficient than the theoretical maximum. Even in the case of ϵ = t = 0.01, we only communicate 477 times on average, as opposed to the theoretical maximum of 10000 times.

(2) The effect of ϵ and t on ξ and N com are similar as in the previous example. It is always possible to trade precision for the number of bits and vice-versa.

(3) The choice of t has more impact in the error, as well as the average number of communications than ϵ.

Conclusion

In this paper we presented an event-triggered, data rate constrained observation scheme for continuous-time linear systems with perturbations. After posing the problem statement, the design of the devices that form the communication scheme was explained. A theorem evaluating the upper bound for the minimum bit-rate required to implement this communication protocol was then presented. The protocol was tested via simulations of unicycle-type robots. Through these simulations, the following properties of the observation scheme have been highlighted.

• On average, it was observed in simulations that the number of communications is much lower than the theoretical maximum. This is due to some conservatism in the estimates as well as the fact that the observation scheme functions on an event-triggered basis;

• By properly choosing the parameters of the observation scheme, it is possible to trade-off accuracy for a lower number of bits sent and vice-versa;

• One of the limiting factors of the observation scheme is the usage of a generic local observer. The accuracy of the local observer greatly influences the general precision of the data rate constrained observation scheme.

The continuation of this work includes:

• Using a local observer more adapted to the structure of the system to decrease the total observation error and hence the maximum observation error;

• Using the data rate constrained observation scheme on several mobile robots;

• Adapting the observation scheme to a larger class of nonlinear systems. , we guarantee that the ē(0) starts within that region and hence, (12) holds for all t ≥ 0. ■.

Fig. 1 .

 1 Fig. 1. Structure of setup.

Fig. 2 .

 2 Fig. 2. Evolution over time of the observation error and quantity used in the triggering function, together with the respective bounds for one particular simulation with full state measurement, ω = 0.1, ϵ = 0.01, and t = 0.5.

Fig. 3 .

 3 Fig.3. State-space trajectory of the unicycle robot in the x 1 -x 2 plane for one particular simulation with v l = 0.1, v θ = 0.2, ϵ = 0.01, and t = 0.5.

  and where 0 n×m is the n × m zero matrix. This LMI program is then used to compute K as a function of Y and P, which in turns provides a bound on the norm of the local observation error, as proven in the next proposition. Let (11) have a solution (M * , P * , Y * , γ *

	√ Proposition 1. γ * 2 δ+ γ * 3 ω √
	γ *

i ). Let η := √ 1 and ϵ 0 be chosen smaller than η. Then by choosing the gain of the local observer as K = P -1 * Y * , the local observation error satisfies:

Table 1

 1 Results for various ϵ with t = 0.1. ϵ

		0.1	0.05	0.02	0.01	0.005
	ξ	0.5128	0.4625	0.4323	0.4222	0.4172
	N com	2.288	5.606	9.993	12.635	14.392
	N bits	4	5	6	7	8

Table 2

 2 Results for various t with ϵ = 0.05.

	t	0.01	0.1	0.2	0.5	1	2
	ξ	0.433	0.462	0.485	0.522	0.568	0.639
	N com	11.719	5.60	1.660	0.493	0.108	0.008
	N bits	4	5	5	5	5	5

Table 3

 3 Results for different choices of ϵ and t with locally fully observed states.ϵ

		0.05		0.01
	t	0.5	0.1	0.5	0.05	0.01
	ξ	0.331	0.200	0.290	0.130	0.0915
	N com	16.15	47.97	21.12	120.26	477.517
	N bits	4	3	6	5	4

  equation: γ * 1 ē⊺ ē, γ * 4 L 2 ē⊺ H ⊺ H ē, (ϕ(x)-ϕ(x)) ⊺ S ⊺ M * S(ϕ(Hx)-ϕ(H x)), γ * 2 d ⊺ d, and γ * 3 w ⊺ w. We then haveV (ē) = ē⊺ (A + KC ) ⊺ P * ē + ē⊺ P * (A + KC )ē + γ * 4 L 2 ē⊺ H ⊺ H ē + (ϕ(Hx) -ϕ(H x)) ⊺ S ⊺ P * ē + ē⊺ P * S(ϕ(Hx) -ϕ(H x)) -(ϕ(Hx) -ϕ(H x)) ⊺ S ⊺ M * S(ϕ(Hx) -ϕ(H x)) + d ⊺ P * ē + ē⊺ P * dγ * 2 d ⊺ d + w ⊺ K ⊺ P * ē + ē⊺ P * K wγ * 3 w ⊺ w + γ * ē⊺ H ⊺ H ē + γ * 2 d ⊺ d + γ * 3 w ⊺ w + (ϕ(Hx) -ϕ(H x)) ⊺ S ⊺ M * S(ϕ(Hx) -ϕ(H x)) ⇕ V (ē) =z ⊺ Qzγ * ē⊺ H ⊺ H ē + γ * 2 d ⊺ d + γ * 3 w ⊺ w + (ϕ(Hx) -ϕ(H x)) ⊺ S ⊺ M * S(ϕ(Hx) -ϕ(H x)), where z = [ē ⊺ (ϕ(x) -ϕ(x)) ⊺ d ⊺ w ⊺ ] ⊺ and Q 11 = (A + KC ) ⊺ P * + P * (A + KC ) + γ * 1 I n + γ * 4 L 2 H ⊺ H.Clearly, (11) implies that Q ⪯ 0, and we thus have thatV (ē) ≤ 4 L 2 ē⊺ H ⊺ H ēw + (ϕ(Hx)-ϕ(H x)) ⊺ S ⊺ M * S(ϕ(Hx)-ϕ(H x)) +γ * 2 d ⊺ d + γ * 3 w ⊺ . From (11), γ * 4 I p ⪰ S ⊺ M * S, which implies that V (ē) ≤ -γ * ē⊺ H ⊺ H ē + γ * 2 d ⊺ d + γ * 3 w ⊺ w + γ * Assumption 2 implies that (ϕ(Hx) -ϕ(H x)) ⊺ (ϕ(Hx) -ϕ(H x)) ≤ L 2 ē⊺ H ⊺ H ē and thus V (ē) ≤ -γ * 1 ē⊺ ē + γ * 2 d ⊺ d + γ * 3 w ⊺ w.By traditional Lyapunov arguments, we thus have γ *

							1	ē⊺ ē
			-γ * 1	ē⊺ ē -γ * 4 L 2
				1	ē⊺ ē -γ * 4 L 2
		⎡	Q 11		P * S	P *	P * K	⎤
	Q =	⎢ ⎢ ⎣	S ⊺ P * -S ⊺ M * S P * 0 n×p	0 p×n -γ * 2 I n	0 p×m 0 n×m	⎥ ⎥ ⎦ ,
		K ⊺ P *		0 m×p	0 m×n -γ * 3 I m
	-γ *
			1	ē⊺ ē -γ * 4 L 2
	γ * 3 w ⊺ w, which implies that	√ γ * 1 ∥ē∥ 2 ≤	1 2 ∥d∥ 2 + ē⊺ ē ≤ γ * 2 d ⊺ d + γ * √ √ γ * 3 ∥w∥ 2 .
	By using Assumption 1, we thus have the following globally √ √
	attractive region ∥ē∥ 2 ≤ √ √	γ * 2 δ+ √ γ * 1	γ * 3 ω	. By choosing ϵ 0 smaller than
	γ * 2 δ+ √	γ * 3 ω
		γ * 1

with 1 ē⊺ ē-γ * 4 (ϕ(Hx) -ϕ(H x)) ⊺ (ϕ(Hx) -ϕ(H x)).

Appendix A. Proof of Proposition 1

Proof. For brevity, we will drop the dependency on time in the notations of this proof (e.g., ē refers to ē(t)). We start by defining the Lyapunov function V (ē) = ē⊺ P * ē. The derivative with respect to time of this function is V (ē) = ė⊺ P * ē + ē⊺ P * ė. From (10), we have V (ē) = ((A + KC )ē + S(ϕ(Hx) -ϕ(H x)) + d + K w) ⊺ P * ē + ē⊺ P * ((A + KC )ē + S(Hϕ(x) -ϕ(H x)) + d + K w). We add and subtract the following terms to the right-hand side of the previous

Appendix B. Proof of Lemma 1

Proof. Starting from t j , the error ê(t) := x(t) -x(t) has the following dynamics.

We define the Lyapunov function V (ê(t)) := ê(t) ⊺ ê(t). The derivative with respect to time of this function is

We add and subtract the following terms to the right-hand-side of the previous equation:

, where M * is the solution of (15).

] ⊺ , the previous equation can be rewritten as

By using Assumptions 1 and 2, this can further be transformed to

. From the definition of V , and by taking a square root on both sides of the equations, this yields