{'fraction_non_alphanumeric': 0.03506540435065404, 'fraction_numerical': 0.018313218183132182, 'mean_word_length': 4.805655785852144, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 4, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Layered Binary Templating: Efficient Detection of Compiler- and Linker-introduced Leakage

Cache template attacks demonstrated automated leakage of user input in shared libraries. However, for large binaries, the runtime is prohibitively high. Other automated approaches focused on cryptographic implementations and media software but are not directly applicable to user input. Hence, discovering and eliminating all user input side-channel leakage on a cache-line granularity within huge code bases are impractical. In this paper, we present a new generic cache template attack technique, LBTA, layered binary templating attacks. LBTA uses multiple coarser-grained side channel layers as an extension to cache-line granularity templating to speed up the runtime of cache templating attacks. We describe LBTA with a variable number of layers with concrete side channels of different granularity, ranging from 64 B to 2MB in practice and in theory beyond. In particular the software-level page cache side channel in combination with the hardware-level L3 cache side channel, already reduces the templating runtime by three orders of magnitude. We apply LBTAs to different software projects and thereby discover data deduplication and dead-stripping during compilation and linking as novel security issues. We show that these mechanisms introduce large spatial distances in binaries for data accessed during a keystroke, enabling reliable leakage of keystrokes. Using LBTA on Chromium-based applications, we can build a full unprivileged cache-based keylogger. Our findings show that all user input to Chromium-based apps is affected and we demonstrate this on a selection of popular apps including Signal, Threema, Discord, and password manager apps like passky. As this is not a flaw of individual apps but the framework, we conclude that all apps that use the framework will also be affected, i.e., hundreds of apps.

Compilers can also introduce side-channel leakage, which is invisible on the source level, by applying various optimizations with respect to the program's runtime, memory footprint, and binary size. Moreover, link-time optimizations [50] can further optimize binaries in the linking stage. Page [74] showed that dynamic compilation could lead to side-channel leakage in a cryptographic library with constant-time implementation. Simon et al. [94] demonstrated that different optimization levels in common C compilers can break constant-time implementation of cryptographic primitives by introducing timing side channels. Brennan et al. [11] discovered that timing side channels can be introduced by exploiting JIT compilation. Hence, side channels introduced in the development process due to the complex interaction between software components and compilers that are not obvious on the software layer may remain undetected and pose a risk for all computer users.
As a consequence, numerous works explored the automatic identification of cache side-channel leakage. Most of these works focus on cryptographic implementations and aim for the goal of making the code constant-time [19], [79], [63], [13]. More recently, Yuan et al. [116] showed that manifold learning can be used for automated side-channel analysis of media software. For common applications processing sensitive input, e.g., browsers, the situation is less clear, as it is not feasible to linearize and unify the entire instruction stream for different user inputs that trigger vastly different program behavior. Cryptographic implementations must be resistant to repeatable attack attempts, while other form of input, such as user input, is unpredictable and non-repeatable [89]. Such attacks often suffer from a noisy channel, e.g., affected by co-location with other data on the same cache line or prefetching effects due to spatial proximity. Therefore, the state-of-the-art is not to analyze the leakage based on models and theoretical leakage assumptions but to actively use side channels to template (i.e., to profile) the leakage that can be observed [40], [107]. In a cache-template attack the attacker maps binaries as shared memory into the address space of the templating process and profiles which memory locations show side-channel activity upon specific events. In the attack phase, the attacker also maps binaries as shared memory, as this requires no privileges beyond read access. Thus, the two attack phases operate on binary offsets and are entirely unaffected by mechanisms such as ASLR (address-space layout randomization). To achieve a high level of confidence, the templating (i.e., profiling) must be performed on an attacker-controlled system that is identical or very similar to the target system and using the side channel that will also be used for exploitation subsequently. Unfortunately, this comes at a high cost, namely the runtime of the templating. For instance, templating the binary with cache template attacks [40], shared libraries, and memory-mapped files used by the Chrome browser (about 210 MB), would take 113.17 days with the published cache template attack tool [40] on our test system. This leads to an unsatisfying situation, where cache leakage analysis is not part of secure development workflows.
In this paper, we present LBTA, Layered Binary Templating Attack. LBTA uses multiple different layers with different spatial granularities as an extension to cache-line granularity templating. While a smaller spatial granularity is beneficial in the attack phase, it comes at a substantial slowdown in the templating phase. LBTA solves this problem by introducing a previously unexplored dimension into software-based templating attacks. LBTA combines the information of multiple side channels that provide information, e.g., at different spatial granularity, to optimize and accelerate the search for secretdependent activity. Our templating starts with the channel with the most coarse spatial granularity and based on the activity uses more fine-grained spatial granularity to detect the exact location (cache-line granularity 64 B).
Our evaluation of LBTA on state-of-the-art systems shows that a variety of hardware and software channels with different granularity are available. We focus in particular on a combination of a software channel, the page-cache side channel, with 4 kB granularity, and the cache side channel, with 64 B granularity. Page cache attacks are hardware-agnostic [38], resulting in cross-platform applicability, i.e., our templater supports both Windows and Linux with the 4 kB page-cache side channel. We show that this two-layered approach already speeds up cache templating [40] by three orders of magnitude (i.e., 1848x).
We evaluate LBTA on different large software projects, including Chrome, Firefox, and LibreOffice Writer. The most significant finding is a novel security issue introduced by compiler and linker optimizations such as data deduplication during compilation and linking and dead-stripping. Linker optimizations introduce a spatial distance of multiple 4 kB pages between key-dependent data accessed during a keystroke. Using LBTA [96], we find distinct leakage for all alphanumeric keys, allowing us to build a full unprivileged cache-based keylogger using Flush+Reload that leaks all keystrokes from Chromium-based applications involving password input fields, e.g., Google Chrome on banking websites, popular messengers including Signal, Threema, Discord, and password manager apps like passky. Based on our findings, we conclude that multiple hundreds of apps using the Chromium framework are affected [30]. Using Flush+Reload we can mount powerful keyloggers with high accuracy for Chromium-based applications. In addition, we demonstrate keystroke-correlated cache activity on Firefox and LibreOffice Writer. While the cache activity does not reveal the actual keystoke, inter-keystroke timing attacks might be mounted on these targets [95], [81], [117], [26], [40]. We confirm that on Linux, the preadv2 syscall can be used instead of the meanwhile mitigated mincore syscall [38], to perform page cache attacks [51]. However, accurate keylogging using with preadv2 and the page cache attacks are infeasible, as stable results require a delay of 2 seconds between cache activity.
Since existing system hardening techniques, e.g., ASLR (address-space layout randomization), have no effect on our attack, we provide a systematic discussion of the possible mitigation vectors.
Contributions. The main contributions of this work are: 1) We introduce a new dimension, side-channel granularity, into cache template attacks and exploit it to speed up the templating runtime by three orders of magnitude. 2) We show that the leakage discovered by LBTA can be exploited both in hardware (i.e., Flush+Reload) and software cache attacks (i.e., page cache attacks). 3) With LBTA, we discover optimizations in LLVM/clang that introduce side-channel leakage invisible on the source level, namely data deduplication and dead-stripping. 4) Our end-to-end keylogger attack can be applied to Chromium-based software, including Google Chrome, secure messengers like Signal, and password managers.
Responsible Disclosure. We responsibly disclosed our findings to the Chromium project. The underlying issue was rated as 'medium' severity and a CVE will be assigned at the beginning of August 2022. We are working with the Chromium team on resolving the vulnerability and informing all affected parties. In alignment with them, our experiments and tools will be open-sourced after the vulnerability is patched. The patch is already implemented and will be included in the Chromium release M104 in the beginning of August 2022. 2 Outline. In Section II, we provide the background. In Section III, we explain the building blocks of LBTA. In Section IV, we describe the effects during compilation and linking that facilitate or even introduce side-channel leakage, i.e., data deduplication and dead-stripping. In Section V, we evaluate LBTA on different attack targets and show a full end-to-end keylogger attack on the Chrome browser and Electron apps.
In Section VI, we provide a systematic analysis of mitigation vectors. In Section VII, we discuss its implications before we conclude in Section VIII.

II. BACKGROUND
In this section, we explain the necessary preliminaries on hard-and software cache attacks, automated discovery of side channel attacks, and side channels introduced by compiler optimizations.

A. Shared Memory
Operating systems apply various optimizations to reduce the systems general memory footprint. One such optimization is shared memory, where the operating system actively tries to remove duplicate data mappings. An example would be shared libraries, such as the glibc, which is used in many programs, and thus, can be shared between processes. Moreover, with the mmap respectively LoadLibrary functions, a user program can request shared memory from the operating system by mapping the library as read-only memory. Another optimization to reduce the memory footprint commonly used for virtual machines is memory deduplication on a pagewise level. The operating system deduplicates pages with identical content and maps the deduplicated page in a copy-on-write semantic.

B. Deduplication
The concept of deduplication is very generic and can be applied in the context of various memory systems to save memory. For storage systems, one example is cloud storage systems that deduplicate files to minimize the amount of storage required [45], [53]. For main memory, there are multiple mechanisms that lead to deduplicated memory. One is copy-on-write, which avoids duplicating memory in the first place during process creation. A similar effect can be achieved via the operating system's page cache [38], i.e., file-based page deduplication. Modern operating systems also deduplicate the zero page, i.e., many processes can map the same zero page as copy-on-write instead of having their own copies of zeroed memory. However, the most prominent example is data-based page deduplication [98]. With data-based page deduplication, the operating system or hypervisor scans the main memory page-wise and identifies identical pages, e.g., using hashes or byte-wise data comparison. The identical pages are then deduplicated and marked as copy-on-write. In all cases of deduplication, when a user tries to modify the deduplicated memory, it is copied (duplicated) again. All above types of deduplication are known to introduce sidechannel leakage, e.g., file deduplication [45], [4], and also page deduplication [98] also from JavaScript [37], [23] and even remotely [92]. Deduplication has also been a building block for other attacks such as KASLR breaks [112], and Rowhammer attacks [9], [78].
While all above types of deduplication target memory, there is also deduplication in other contexts. In this paper, we focus on a different type of deduplication that has little to do with the above or memory systems in general. We instead focus on deduplication during compilation and linking. The goal of deduplication here is similar, i.e., reducing memory usage. However, the security implications of deduplication during compilation and linking have not been studied so far.
In particular, for SGX, so-called controlled channels have been demonstrated as powerful attack primitives [113], [100], [65] with high spatial and temporal resolution, as well as a very high accuracy. Controlled channels are side channels running with elevated privileges, e.g., kernel privileges, with a typical attack target being secure enclaves, that are protected against regular kernel access.

D. Software caches
On the software level, there are also caches that buffer data from slower memory components in faster memory components. Software caches are used to cache frequent data like web requests in web servers [68], [80], in-memory databases [64], or keep frequently used database records [66]. These caches are limited in their size and follow similar replacement strategies to replace old data, such as LRU eviction [64]. Caches like Nginx's request pool and Memcached [64] were exploited in memory-deduplication attacks [9], [78], [92].
Operating systems use a software-level page cache to speed up accesses on disk-backed data by keeping the data buffered in main memory (DRAM) [34], [38]. If the page cache is full, a page-replacement algorithm is used to replace pages and swap them out to disk [14], [49]. Linux and Windows offer functions to verify whether a specific virtual address is resident in memory or not, namely mincore and QueryWorkingSetEx,Shared,ShareCount respectively. Gruss et al. [38] showed that cache attacks can be applied to the page cache by using either these functions or by measuring timing differences. Consequently, the Linux kernel developers hardened the mincore implementation to only return page cache status information if the calling user can write to the underlying file, mitigating cache attacks using the mincore syscall. The Windows kernel developers further restricted lower privileged processes to directly obtain information about the working set form higher privileged processes [38].
On Linux, however, the system call preadv2 can still be used to mount cache attacks [51] in the same way as with the mincore syscall: Using the RWF_NOWAIT flag, an attacker can observe whether a page is resident in the page cache or not, yielding the same side-channel information as mincore.
The results of the preadv2 templating attacks can be found in Section V.

E. Automated Discovery of Side Channel Attacks
Templating attacks have been first shown and mentioned on cryptographic primitives running on physical devices [19], [79], [63]. Brumley and Haka [13] first described templating attacks on caches. Doychev et al. [29] presented a static analyzer that detects cache side-channel leakage in applications. Gruss et al. [40] showed that the usage of certain cache lines can be observed to mount powerful non-cryptographic attacks, namely on keystrokes. Lipp et al. [61] showed cache attacks and cache template attacks on ARM. Van Cleemput et al. [101] proposed using information gathered in the templating phase to detect and mitigate side channels. Wang used symbolic execution and constraint solvers to speed up cache templating of cryptographic software [108]. Schwarz et al. [87] demonstrated template attacks on JavaScript to enable host fingerprinting in browsers. Weiser et al. [110] and Wichelmann et al. [111] showed that Intel PIN tools can be used to automatically detect secret-dependent behavior in applications, especially in a cryptographic context. Wang et al. [107] presented a similar automated approach to detect keystrokes in graphics libraries. Carre et al. [15] mounted an automated approach for cache attacks driven by machine learning. With that approach, they were able to attack the secp256k11 OpenSSL ECDSA implementation and extract 256 bits of the secret key. Brotzmann et al. [12] presented a symbolic execution framework to detect secret-dependent operations in cryptographic algorithms and database queries. Li et al. [59] demonstrated a neural network to perform power analysis attacks automatically. Yuan et al. [116] demonstrated that manifold learning can be used to detect and locate side-channel leakage in media software.

F. Compiler-introduced Side Channels
While developers typically focus on the source code level and care is taken to not introduce side channels there, the compiler translates the source code to a binary, essentially a different language. However, this step can introduce program behavior that is not visible on the source level and introduces or amplifies side-channel leakage. Page [74] demonstrated that dynamic compilation in Java leads to power side-channel leakage in a side-channel-secured library. Simon et al. [94] showed that mainstream C compilers optimizations can break cryptographically secure code by introducing timing side channels. Brennan et al. [11] showed that timing side channels can be introduced by exploiting JIT compilation.

III. Layered Binary Templating Attack
For non-cryptographic applications, templating approaches [40], [61], [107] can be used to find realworld exploitable leakage. However, for large binaries like the Chrome browser with multiple shared libraries (220 MB), templating with fine granularity, e.g., a cache line, becomes impractical. Therefore, we present LBTA, a layered approach taking advantage of the coarser granularity of some side channels, which is typically considered a disadvantage for the attacker. In this section, we present the high-level view on LBTA and show how LBTA reduces the templating runtime by three orders of magnitude (i.e., 1848x). We discuss implementation details and design decisions for our proof of concept implementation. Our threat model follows the standard template attack threat model [40], that distinguishes between the templating and the exploitation phase.
Threat Model in the Templating Phase. For the templating, also known as the profiling phase, we assume the attacker was able to obtain a reasonably similar system, i.e., with the same side channels as the victim system, such as the page cache and CPU cache. The attacker has full control over this system and can template the same binary version, e.g., obtained from package repositories or the vendor website, that also runs on the victim system. The attacker can create templates for different binary versions and applications to have a suitable template in the exploitation phase subsequently. In this phase, the attacker can also use any privileged or unprivileged mechanisms for the templating or improve its detection accuracy.
Threat Model in the Exploitation Phase. In the exploitation phase, the attacker runs an unprivileged attack program on the victim's system, possibly under a separate user account. Hence, we assume the victim application is started independently by the victim user, and cannot be started, stopped, or debugged by the attacker. This also excludes "preloading", which, e.g., on Wayland (the default Ubuntu display server), would allow monitoring all inputs to the application [5]. For non-Wayland systems, we assume that the attacker cannot use other keylogging techniques (e.g., on X11 [3]), or Windows (e.g., using the getasynckeystate API call [106]), e.g., due to system hardening or enforced security policies. For our keylogging scenario, we assume that the victim user performs keystrokes manually and does not use scripted input generation, e.g., autofillers or password managers. Figure 1 illustrates the steps of LBTA. First, the attacker templates the library and creates templates for the cache usage of different keystrokes (step 1). After the templating phase, the attacker starts monitoring the software or hardware cache usage. Depending on the cache activity, the attacker can infer if input was given or, in the optimal case, distinguish the keystrokes.

C. Exploiting Different Spatial Granularity
One novel aspect of LBTA is to use the different spatial granularity of different side channels to our advantage. The main focus here is on the templating phase, i.e., the threat model for the templating phase applies. In the following, we discuss how we extend cache templating from cache-line granularity, as used in previous work [40], over 4 kB page granularity [38] and 2 MB page granularity, to a practical and generic multi-layered approach. Our technique also extends to dimensions of 1 GB steps and beyond but we are not aware of real-world victim binaries of such large size.
64B Granularity. Previous cache template attacks [40] used cache-line granularity (64 B). One disadvantage of this approach is the runtime of the templating phase. When templating a single cache line with Flush+Reload, we observe an average runtime of 490 cycles (n = 1000000, σ x = 20.35%). On a 4.0 GHz CPU, this would take 122.5 ns. The Google Chrome binary has a file size of about 210 MB leading to 2 949 120 addresses to template with Flush+Reload. This leads to a runtime of 0.36 s for templating every cache line once. However, Gruss et al. [40] describe that multiple rounds of Flush+Reload are required to get reliable cache templating results. Running an Intel 6700k CPU at 4.0 GHz with a Ubuntu 20.04, templating 1 MB of the Chrome browser (version 100.0.4896.60) with the provided implementation of Gruss et al. [40], we observe a runtime of 817.652 s for 1 MB and a total runtime of 1.98 days for the full binary, including shared libraries, of 210 MB. Moreover, this templating tool only reports whether a certain address was cached or not and does not match the cache hits with the entered keystrokes. To template, for instance, the 57 different common keys sequentially with the method by Gruss et al. [40], we would need an impractical total runtime of 113.17 days to obtain useful templates. We conclude that such an approach is not feasible for browser developers as the code base changes frequently, and releases sometimes occur on a monthly basis [20].
4kB Granularity. Page cache attacks exploit the operating system page cache, which works at a coarser granularity of 4 kB [38]. Page cache attacks have the advantage of working independent of the underlying hardware. To identify the exact memory locations causing leakage, they also resorted to templating. However, they did not combine this information with timing differences from hardware caches.
Our intuitive idea here is to combine the 4 kB-granularity side channel with the more fine-grained side channel into a two-layered approach. Hence, we do not template all cache lines on a 64 B granularity but instead pre-filter memory locations on a 4 kB granularity. Instead of 2 949 120 memory locations, we then only need to monitor 46 080 memory locations for the Chrome example, i.e., a templating runtime speedup of at least 64. In addition, the templating phase on the 4 kB granularity level implicitly identifies locations exploitable via the page cache.
In the templating phase, the attacker is not restricted as the code runs on the attackers own machine (cf. Section III-A). Similarly to previous work, we can use the page cache side channel or privileged channels, e.g., controlled-channel attacks [113] via page-table bits [100]. We used the idle bit as page tracker for Google Chrome (cf. Section III-E) to be particularly useful as we have only a runtime of 1.47 hours for all 57 key strokes.
2MB Granularity. While the two-layered approach already brings a significant runtime speedup, our approach is more generic and extends to further layers. Again, in the templating phase, the threat model (cf. Section III-A) permits the use of privileged channels, e.g., controlled-channel attacks, but this time on the page directory layer. Each page-table layer provides referenced bits that are set by the hardware when a location in this region is accessed. This 2 MB-granularity side channel is also exposed via various side channels [39], [57], [102], [60]. However, the activity on 2 MB pages can be observed via the Page Middle Directory paging structure and the referenced bit. We use the tool PTEditor [88] to clear the referenced bit in the PMD. Checking and clearing the referenced bit of the PMD, i.e., a 2 MB page, leads to a runtime of 661.965 ns (n = 1000000, σ x = 0.049%). Similar to the templating with 4 kB granularity, we assume that multiple repetitions are required to observe stable results and remove false positives. Hence, to template the 57 different common keys in Chrome with 20 repetitions per key, we estimate the total templating to be about 0.15 seconds.

D. Beyond Huge Pages
The concept of LBTA extends to arbitrarily coarser granularities as long as a channel exists.
1 GB Granularity. For the 1 GB granularity level, we experimentally validated that we can again use controlledchannel attacks [113], [100], albeit this time on the pagedirectory-pointer-table level. On this level, one entry (and thus one referenced bit) covers a 1 GB region. Following a similar approach as for the previous levels, we use PTEditor to template and clear the referenced bit, for the single offset in a 1 GB range. The runtime for checking and clearing the referenced bit in the PUD is the same as for the PMD (661.965 ns (n = 1000000, σ x = 0.049%)). Note that this layer of LBTA may become relevant in the future with constantly growing binaries and libraries. 3 512 GB and 256 TB Granularity. The intuitive extension of our approach also uses the referenced bits on higher page-table layers, i.e., the page-map level 4 to template in 512 GB steps, and the page-map level 5 (if available) to template in 256 TB steps. We verified that we can indeed observe activity in this range via controlled-channel attacks [113], [100], i.e., via the referenced bits, showing that LBTA can be extended to a 5-layer templating phase. The runtime for checking and clearing the referenced bit in the PML4 is the same as for the PUD (661.965 ns (n = 1000000, σ x = 0.049%)).
We emphasize that scanning layers that exceed the binary size, e.g., the 1 GB layer for a 180 MB binary, provides no additional information and does not reduce the search space, as the search will always proceed to the next smaller layer for the entire memory range then. Therefore, in the evaluation, we skip all layers that exceed the binary size.

E. Templating Phase Implementation
The high-level idea is that the templater tracks the usage of pages and then actively filters out pages that are not related to keystrokes to reduce the search space of pages to template and, as a result, reduce the overall runtime of the templating. We implement our templater in Python, and provide it as open source in our Github repository [2]. The templater takes as input the set of different keys, the PID or process names that should be monitored, and the number of samples per key.
Algorithm 1 summarizes the steps of the templating. First, the templater runs a warmup phase, where all keystrokes to template are entered once to load all related memory locations into RAM. Then the templater collects all the memory mapping information from all files from the target processes where activity has been found. These memory mappings include all shared libraries. The templater generates random key sequences based on the set of keys to template. For each key in the sequence, the templater iterates over all the memory locations on the current granularity level, and resets the access information, i.e., resets the referenced or idle bit, or flushes the cache line depending on the side channel used. Based on the number of samples performed, the templater computes the hit ratio for each location. Subsequently, the templater repeats this step for all memory locations above a specific hit ratio with the next lower spatial granularity. With this search strategy, the templater continues down to the lowest level, where only regions are templated that showed activity on coarser granularities. On the lowest level, the templater then obtains a hit ratio for each single cache line.

Algorithm 1: LBTA Templating Algorithm
Input: Set of keys K, target PIDs P n , number of samples N Output: hit ratio matrix of all memory mappings H 1: Enter all keys in K once // Warmup 2: Collect all valid memory mappings of P n (possibly from previous layer) 3: for i = 0; i < N ; i + + do 4: for each k ∈ K do 5: Reset memory mappings (reset referenced/idle bits or flush) 6: Enter key k 7: Check state for all present memory mappings (via interface or timing) 8: Compute hit ratios for k and update H k 9: end for 10: end for 11: return H, and repeat algorithm for next layer Linux. On the upper layers, we start by obtaining the memory mappings for the target process. On Linux, we read these mappings from procfs (with root privileges in line with the threat model). We group the memory locations then according to the most coarse granularity we use in our templating. By using the referenced-bit side channel according to Algorithm 1, we narrow down the set of memory locations for the next layer.
Windows. On Windows, we can also obtain a list of memory mappings using the EnumProcessModules PSAPI call, which lists all loaded libraries and executable programs. To retrieve the actual sizes of the libraries and executables, the GetModuleInformation PSAPI call is used. Subsequently, we follow the same process using the referencedbit side channel as on Linux to narrow down the set of memory locations using Algorithm 1. Subsequently, we continue with the next layer.
1) 4 kB Page Granularity: While for the upper layers, we used PTEditor [88] to read the referenced bits, we implemented a more optimized approach for the page granularity.

Linux.
We implement a page usage tracker which iterates over all active mappings, reads the idle bit for the corresponding physical page from /sys/kernel/mm/page_idle/bitmap and checks if the page was accessed. We start by resetting the bit so that the page usage tracker is ready. We use the Python3 keyboard library to inject keystrokes into an input field. After the templater performs the sequence of keystrokes, we check all pages that are still in the candidate list for activity. If we now observe a 1 at the page offset in the bitmap, the page was not accessed. Conversely, if we observe a 0 at the page offset, we reset the page offset, and add it to the set of correlated pages to track on the next layer. Note that this approach is fully hardware-agnostic as this feature is implemented in software in the Linux kernel. After each iteration, we reset the state again by marking the pages as idle again and repeat the measurements.
In case of a sequential read access pattern, the Linux kernel speculatively prefetches further pages of the same file after a new page was added to page cache. This optimization is called readahead [44]. On Ubuntu 20.04 (kernel 5.4.0), the default read-ahead size is 128 kB and can be found in the sysfs (/sys/block/ <block_device>/bdi/read_ahead_kb). For filemappings the kernel performs a different optimization called read-around. 4 There, the kernel prefetches pages surrounded by the page causing the pagefault e.g., 16 pages before the page causing the pagefault and 15 pages after. To reduce triggering read-ahead prefetching for sequential reads, we use the madvise system call with the MADV_RANDOM flag to indicate a random read order.
Overlapping event (i.e., keystroke) groups for the current candidate page and pages that might trigger the readahead of the current candidate page could cause false positives in the Linux case. In addition, if the number of readahead suppress pages is too small, false positives can occur. Our classifier tries to reduce the number of false positives by checking out the read-ahead/read-around windows and systematically rule out other keystrokes. Based on the results of the templater, the classifier actively accesses surrounding pages from the target page to suppress the read-ahead/read-around optimization. Note that the read-ahead and read-around windows might overlap for some keys. If the keys to template are not on the same 4 kBpage, we can still distinguish two keys by checking the first and last surrounded pages being accessed. The templater actively creates warnings in the templating phase in case the keys are still indistinguishable.

Windows.
Windows uses a different page replacement strategy with global and local working sets [84]. To build the page usage tracker on Windows, we use the PSAPI call QueryWorkingSetEx and monitor the Shared,ShareCount and Valid flags. If the page is marked as valid and shared and the share count is larger than 1, we mark the page as used. To perform the reset, the EmptyWorkingSet PSAPI call is used to remove the pages from all workings sets. This PSAPI call is only available for unprotected processes, which is no issue during the templating phase (cf. Section III-A).
On Windows, we observed no prefetching optimization within working sets. Therefore, read-ahead is no problem for measuring the hit ratio and detecting the exact offset on this level. Alternatively, the templating could also be performed via controlled side channels [113], [32], [93], tracing tools such as Intel PIN, machine learning [107], [15] or architecturally monitoring the accesses of pages using PTEditor [88].
Classifier. We further try to restrict the search space further on the 4 kB level. On the 4 kB level, we collect the page-hit ratios for all events (i.e., keys) and pages, showing the link between event and observable page hit. The templater also templates a dummy idle event that sleeps for 30 seconds to measure which hit ratios are above the system's noise floor. This idle event will not be linked to any page hit but rather should represent unrelated noise that the templater might have missed during the sampling of the other events. Our classifier links events or groups of events with single page hits to keep the number of observed pages as low as possible. This is a trade-off between search time and completeness of the search that can be chosen differently for any LBTA on any target application. Furthermore, a more sophisticated attack could increase detection accuracy from monitoring multiple pages or cache lines for each event. However, we decided to use the search-time-optimized path, as side-channel attacks typically cannot observe an arbitrary amount of memory addresses anyway, i.e., we focus on a more practical set of leaking addresses.
The algorithm to find a suitable page hit describing an event e works as follows: 1) We take the vector of all page-hit ratios related to event e and subtract the sum of the page-hit-ratio vectors of all other events (noise) from it. The resulting vector describes how strongly accesses to a certain page (index in the vector) are correlated with an event e. 2) We select the page with the highest score as a candidate. a) Should the resulting candidate fail to fulfill our minimum score requirements (i.e., not above the locationspecific noise floor), our algorithm merges events to find a suitable page to recognize this group of events. b) We treat the target event and the M −1 remaining events (exluding the idle event) with the highest page-hit ratios per page as one group. The difference is that we now have an event group E = {e 1 , ..., e M } instead of a single event. The group's score is the minimum score of its events. After merging, we use the same classification scheme as in step 1. c) Should we still fail to find a suitable page, we return to step 2.1, i.e., we merge further events until we succeed, or we end the classification for the event. 3) While running, the classifier also collects information on potential read-around prefetching pages to filter them out.
After a successful classification, the attacker has a mapping of pages to events (i.e., key) and groups of events (i.e., groups of keys). Subsequently, we can use this information and the trace from the side-channel attack to build our keylogger.

IV. COMPILER-AND LINKER-INTRODUCED SPATIAL DISTANCE IN BINARIES
Before we evaluate LBTA, we present one significant leakage-facilitating effect that we discovered while applying LBTA on a variety of targets. This effect is particularly critical as it originates in compiler optimizations in LLVM/clang that are enabled by default and cannot be disabled via compiler flags. Compiler optimizations aim for a minimal program runtime, small memory footprint, and small binary size. Moreover, linker optimizations try to further optimize the binary in the linking stage. This is especially useful for large software projects such as browsers. We primarily found two effects to facilitate cache side-channel leakage: One is data deduplication during compilation and linking, the other is the first-come-first-serve data placement introduced by the deadstripping mechanism. While memory deduplication at runtime has been explored as a security risk already (cf. Section II-B), data deduplication (e.g., of strings) during compilation is not widely known and its security implications are entirely unexplored. The security of constant-time implementations has been analyzed for side channels being introduced by compilers [74], [101], [94], [11]. In this section, we first show that dead-stripping (cf. Section IV-A) can facilitate and amplify side channels on read-only strings used in C/C++ programs. We then show that deduplication during compilation (cf. Section IV-B) and linking (cf. Section IV-C) can amplify this effect by increasing the chance that secret-dependently accessed victim data is placed in an attacker-facilitating way. In addition to compiler optimizations, deduplication can als be performed at the linking stage. The spatial distance between secret-dependent accesses can be introduce by both compiler and linker optimizations. We present two scenarios that we also found in widely used real-world applications, where the placement of read-only data, especially strings, amplifies sidechannel leakage dramatically.  Lookup tables are frequently used in applications to speedup memory accesses and store constant data like locality strings. For the developer, it is not transparent how constants are stored in the compiled binary. Thus, even if the code seems to hide a cache-side channel on 64 B granularity, the compiler might reorder strings and add more spatial granularity between items of the same lookup table. One optimization to reduce the binary size is to only populate the read-only data section if the compiler observes that only certain indices of a lookup table are accessed. Figure 2 illustrates how data can be re-ordered in the use case of dead-stripping. If the developer uses a macro to dynamically populate a lookup table, e.g., with key mappings or similar, compilers do not insert all elements into the read-only section of the binary to reduce the binary size. Listing 1 lists an example of code that seems to have co-located strings mappings array in the .rodata section. However, as the compiler is free to populate the readonly section in the binary, it is possible that the compiler introduces leakage here that is not visible on the source level. While without this optimization, an attacker could not distinguish whether KeyA or KeyB was accessed with Flush+Reload in the original code snippet. The compiler creates a spatial distance exposing this secret information to the 0x21000 0x22000 0x23000 0x24000 Deduplicate strings Fig. 3: String deduplication in the compiler causing spatial distance in .rodata section of the binary.
attacker. We evaluate our test program on Clang 10 and GCC 9.4.0 with the optimization levels O0-O3,Os. For Clang, we observe that on every optimization level and also without optimizations, the padding string is between the DataA and DataB strings, i.e., DataA.<64-byte-string>.DataB.. The . indicates a NULL-byte in the memory layout for C strings. Clang compiler traverses all functions and populates the .rodata depending on the fixed indices for the array lookup. GCC with the O0/O1 flags populates the .rodata directly with all strings from the mappings array, i.e., DataA.DataB.<64-byte-string>. Therefore, an attacker would not be able to observe which cache line was accessed. For the other optimization levels in that concrete example, the small strings DataA,DataB would be directly stored as immediate in the binary, e.g., "mov DWORD PTR [rsp+0x50], 0x756c6156" and then the full string on the heap is allocated.

B. Data Deduplication during Compilation
Another optimization facilitating cache attacks, also in combination with the dead-stripping we just discussed, is data deduplication during compilation. Deduplicating strings can reduce the binary size significantly but also the memory resident size when running the program, as strings do not have to be kept in memory multiple times. Figure 3 demonstrates how string deduplication can introduce spatial distance in sections of the binary, for instance, the .rodata section. C/C++ compilers deduplicate strings that occur more than once in the source code. Listing 2 illustrates a situation where the string deduplication optimization can be used. Both the lookup table mappings and the function string_funcA contain the string DataA. Since the compiler again traverses over the functions and DataB is first inserted into the .rodata section. Again a constant padding string could cause DataA and DataB to be located in different cache lines. Before the compiler inserts DataB (mappings [1] in string_funcB), the compiler checks for duplicates and only points to the existing occurence of DataB in the .rodata for all future usages. Again we evaluate this code constellation for GCC and Clang. For Clang, we observe again for all optimizations levels the ordering DataA.<64-byte-string>.DataB in the .rodata section. For GCC, we observe the same result that for optimization levels O0/O1, both values are populated next to each other in the .rodata (DataA.DataB). Again for the higher optimization levels, the small strings are encoded as immediates. Listing 2: Strings are deduplicated in the binary and could lead to spatial distance between readonly-strings in the same array.
C. Deduplication in the linking step.
As we showed, string deduplication can cause spatial distance between strings and enable side-channel attacks in the compile step. For large software projects such as the Chromium project, it is important also to save time while linking together a large amount of object files. However, for such large software projects, the runtime of the linker is crucial. Linkers are also merging strings as an optimization in the linking time. To perform fast lookups of strings in the linking step, hash tables are used [83]. Since 2017, lld uses multiple hash tables instead of one large one to enable concurrency. Concurrency in the linking step brings a speedup in the linking time. However, as there are multiple tables, inserting merged strings can cause a different layout for strings in the .rodata section than in the final linked binary. Figure 4 illustrates how the concurrent merging can lead spatial distance in the final binary. In the highest optimizations of lld linker, i.e., -O2[69], the linker merges duplicate substrings contained in larger strings. The smaller substring will be removed, and the tail of the larger string used to index the substring. The security implications of string deduplication need to be considered in software projects since large spatial distance between secret dependent values such as different key inputs can lead to leakage of all user input, as we show in Section V.

V. EVALUATION
In this section, we evaluate our templater on large binaries such as browsers that have not been targeted with templating attacks so far. We also focus on widespread Chromiumbased products and demonstrate that they are susceptible to LBTA. We analyze the root cause for the leakage and show that it is caused by a compiler optimization. Table I lists all the evaluated applications, including the Chromium-based browsers and applications, Firefox and LibreOffice Writer. Templating of HTML form input fields Google Chrome. We first run our templating tool while generating keystrokes. We run our templater on an Intel i7-6700K with a fixed frequency of 4 GHz running Ubuntu 20.04 (kernel 5.4.0-40) on Google Chrome version 100.0.4896.60. To get more accurate results during the templating phase, we recommend dropping the active caches before the execution of the templater via procfs (/proc/sys/vm/drop_caches). Moreover, we blacklist file mappings from the /usr/share/fonts/ as they lead to unstable results during the evaluation phase. Our templater traces 57 different key codes of a common US_EN keyboard in HTML password fields. For each key code, we sample 20 times. On average, we observe a runtime of 1.47 hours (n = 10, σ x = 0.33%) for 57 key codes, including the time for key classification. For a single character, the runtime is 92 seconds. We use the ldd to find all shared libraries used in Google Chrome to determine the overall file size of libraries to template. Including the main binary, the total size of memory mappings to scan is 209.81 MB. We estimate the runtime of the public implementation for cache template attacks [40] to 113.17 days. Our templater brings a speedup in the templating runtime of factor 1484. Using the proposed optimizations of Gruss et al. [40] leveraging parallelism in the templating phase, we can achieve a runtime of 17 s per megabyte. Thus, the templating time could be improved to 2.35 days. However, this approach appears to be noisier and was not merged in the public implementation of cache templating attacks [40].
Leakage Source in Chrome. As we discovered the page offsets related to the different keystrokes, we want to find the exact cache line causing the cache leakage. We extend our monitor with Flush+Reload to determine the cache line within the page. To speed up the templating time and reduce the noise for cache lines, we disable most of the Intel prefetchers by writing the value 0xf to MSR 0x1a4 [105]. We map the Chrome binary as shared memory and perform Flush+Reload on all mapped cache lines to determine the corresponding cache lines for each key.
We analyze the Chrome binary and lookup the offsets causing the leakage for a specific key stroke. Each cache line causing the leakage of a certain character contains a string for the key event, e.g., "KeyA". By reading Chrome's ELF header, we observe that all offsets lie in the read-only data (.rodata section of the binary. The leakage source are keydependent accesses to the key code strings in the dom code .rodata  0x001e, 0x0000, "KeyA", US_A);. As these strings appear multiple times at different locations in the code, the location in the .rodata depends on the compiler. Figure 5 illustrates the leakage source for a user typing in a certain character and the corresponding DOM CODE for the UI event.
To verify if the leakage is related to string deduplication, we download the Chromium source, disable the string deduplication -fno-merge-all-constants and rebuild the Chromium browser. We still observe, that the single keystrokes are spread over multiple pages in the .rodata section.
As a next step, we analyze the compiled object files after the build process. We observe that the created object file keycode_converter.o still contains all the key event strings adjacent to each other in the binary. This indicates that the linker introduces the spatial distance between key event strings.
We perform a binary search on older Chrome binaries from a public Github repository containing archived Chrome Debian packages [109] to see when the spatial distance for key event strings was introduced. As a result, we observe that between version 63 and 64 of Chrome (year 2017), the single key event string was placed in the .rodata at different 4 kB pages. According to [83], the linker optimizations have been constanly improved since 2017. As discussed in Section IV, the parallelism in string deduplication can also cause spatial distance between key events. Disabling the string merging optimization of the linker with -Wl,-O0 for a current Chromium version removes the spatial distance between the key event strings. Re-enabling the string merging optimization of the linker, i.e., -Wl,-O1, the spatial distance reappears as strings are again deduplicated. This confirms that one of the effects we exploit is introduced by the linker.
In comparison to state-of-the-art keyloggers on Linux like xkbcat [3], our keylogger does not rely on running as the same user within the same X-session. We verify this by running our keylogger as a different user and can still recover the keys from the Chrome browser. Note that more sophisticated cache attacks like Prime+Probe can be performed to enable JavaScript-based attacks [71], [104], [1].
Keylogging in Google Chrome with Flush+Reload. We run our monitor in three experiments for 180 seconds with all 5 https://source.chromium.org/chromium/chromium/src/+/main: ui/events/keycodes/dom/dom code data.inc lowercase alphanumeric characters and observe cache activity for every single keystroke. The first experiment runs with fast user input with 1 ms between each keystroke. We count cache hits following a keystroke as true positives if they occur on the cache line that is correct according to our template, and as false positive otherwise. To obtain the number of false positives, we run the monitor in a second experiment without performing any keystrokes in the input field, i.e., idling. To complete our data on false negatives and true positives, we run the monitor in a third experiment while performing user input with 1 s between each keystroke. Over the total 540 second measurement time frame, we observed no false negatives. Figure 9 (Appendix) shows the cache-hit ratio for the cache lines detecting lowercase letters in Chrome. Figure 6 shows the cache-hit ratio for the cache lines detecting numeric digits in Chrome. As shown from Figure 6, the different digits can be highly-accurately classified. As can be seen, digit 9 causes constant noise for all the different keys as in that version of Google Chrome. The cache-line is constantly accessed also in an idle state. The F-Score is the harmonic mean of precision and recall. Figure 7 illustrates the F-Score for all alphanumeric characters. From all the 36 alphanumeric keys, this is the only character causing constant noise on Google Chrome. Moreover, we observe that a single keystroke causes up to three cache hits. These cache hits could be related to the window events key_up,key_pressed and key_down. To avoid printing the same character multiple times, a cache miss counter between the keystrokes can be used [40]. Note that multiple cache lines can be considered to further increase the accuracy of the keylogger [61], [107], [15].
Keylogging with the page cache. To demonstrate that the Chrome leakage is not specific to a certain CPU, we run our keylogger on around and read-ahead optimization as explained in Section III-E. The keylogger uses the keystroke template for the main Chrome binary and monitors the page cache utilization for the corresponding pages using the preadv2 syscall. It then reports the detected activity as keystrokes and subsequently evicts the page cache. While the page cache attack using the mincore syscall was able to observe keystrokes on a fine temporal granularity, we observe that using preadv2 comes with practical limitations. In particular, with large eviction set sizes, guessed by the attacker, we conclude that only very slow keyboard interaction with gaps of 2 s and more can be observed. However, our evaluation of the page-cache side channel is generic and would also apply to scenario where the mincore syscall is available, which allowed fast and nondestructive continuous probing.
Based on the page cache accesses, we compute the pagehit ratio for Google Chrome over the page cache. Figure 9 (Appendix) shows the page-hit ratio for the page cache detecting alphanumeric letters in Chrome. For the Chrome version, we observe that the characters b,m,9,h,y,x are grouped and cannot be uniquely distinguished. We again perform the experiment in three phases to determine true positive, false positive, and false negative rate, by simulating fast, slow, and no user input. Figure 8 shows the F-Score for all alphanumeric characters running the page cache attack. While most characters have very high F-Scores, the character group b,m,9,h,y,x has a lower F-Score due to false positives when other keys are pressed. Also, same as in the Flush+ Reload attack, the character 9 suffers from a high number of false positives, negatively impacting the F-Score.
Electron. As we observed the leakage of keystrokes within the Chrome binary, we further analyze Chromium-based applications like the Electron framework. As Chromium-based applications use the same handling for keystrokes for all applications, we can directly scan the .rodata section for the keystroke mappings to find the offsets. We evaluate the templates on Chromium, Threema, Passky, VS-Code, Mattermost, Discord and observe similar leakage rates to Google Chrome with F-Score of over 85 %. Table I contains the high F-Scores for the different applications. We run our monitor on the lowercase alphanumeric keys and observe a similar leakage rate with Flush+Reload. Based on these very clear results, we deduce that in principle all Electron applications are susceptible to LBTA and full key recovery attacks.
Chromium Embedded Framework. The Chromium Embedded Framework (CEF) is widely used and another interesting target for LBTA. While Electron directly uses the Chromium API, CEF tries to hide the details of the Chromium API [31]. CEF is actively run on more than 100 million devices [18]. We target Spotify, and the Brackets editor application, which are both based on CEF. To attack a CEF application, an attacker needs to read out the .rodata section from the shared library libcef.so. We run our monitor again with Flush+Reload and observe an F-Score of 0.96 % over the lowercase alphanumeric characters. For Brackets (1.5.0) we observe, that the libcef.so was built with an older linker version as the different key-event related strings for the lowercase alphanumeric characters are co-located in three different cache lines. Therefore, we consider all CEF applications to be susceptible to cache templating in principle. We observe an F-Score of 94 % for detecting key events. However, we also observe that hardware prefetching practically thwarts the distinction of different blocks in this scenario more than in the other attack scenarios, leaving only inter-keystroke timing attacks as an option for the attack phase.
Firefox. We also templated the Firefox binary with LBTA and identified locations with cache activity upon keystrokes. While we observe cache activity for each keystroke in the shared library libxul.so (offset: 0x332d000), we did not find leakage to distinguish keys reliably. Firefox uses a completely different build system, i.e., optimizations such as data deduplication and dead-stripping may still be applied but will not behave exactly the same as with LLVM/clang. However, using the found binary offset, an attacker can determine whether a user is typing and perform an inter-keystroke timing attack [95], [81], [117], [26], [40] to recover the keystrokes. We run the monitor again and probe the address that has the most hits within the page on different keystrokes. The accuracy we observed for such an attack is 96 %.
LibreOffice Writer. We profile the LibrefOffice Writer version 6.4.2 on our Linux setup. Our profiler shows that the library libQt5XcbQpa.so.5.12.8 (offset: 0x51000) offset reveals cache activity on all letters but no digits. The library libswlo.so (offset: 0x53e000) shows cache activity on keystrokes reliably, with an F-Score of 1. Again, interkeystroke timing attacks can be performed.
Chrome on Windows. On Windows, we tested Chrome versions 103.0.5060.53 and 103.0.5060.114. Our evaluation runs on a notebook equipped with an Intel i5-4300U running Windows 10 (1803, Build 17134.1726). We use the LoadLibrary function to load libraries and create a shared mapping between the attacker and victim applications. Using the key event strings, we directly find the offsets in the DLL file. We observe that in the chrome.dll (offset: 0xa4ee000) the different key bytes are co-located instead of having a spatial distance of multiple 4 kB pages. The Chrome build on Windows uses a different compiler and linker, and, thus, the string merging optimization might behave differently or is even turned off. Running our cache monitor using Flush+Reload we do not observe any cache leakage on the DLL file. The grouped keys there are KeyA-KeyF,KeyG-KeyS,KeyT-Digit4 and Digit5-Digit9. Again, the prefetchers on the evaluated CPU practically thwart the distinction between the different groups of keys. Running a similar experiment as on Linux, we observe a F-Score of 0.99 %.
In addition, we use our profiler to observe cache activity on other locations. The DLLs msctf.dll (offset:0x45000)) and imm32.dll (offset:0x3000) also correlate to user input in Chrome on Windows. These two libraries are mainly used for user input methods and the text management. Therefore, using Flush+Reload inter-keystroke timing attacks are possible on Chrome on Windows.
Search bar. Templating user queries in the browser would tremendously reduce the privacy of browsers. Running the templater on the search bar of Google Chrome 103.0.5060.53 revealed that the search bar uses a different method to load the keys and there is only a single page (offset: 0x91d4000) in Google Chrome with cache activity upon keystrokes. Based on our results, we conclude that the search bar does not use the same internal structures for key events as HTML input data. Still, the leakage we discovered enables inter-keystroke timing attacks on keystrokes. Running the profiling experiment with all alphanumeric, we achieve a F-Score of 0.99 % for detecting key presses.

VI. MITIGATION
In this section, we discuss different mitigation vectors that could prevent the leakage. Nevertheless, we want to emphasize that preventing leakage on such a broad scale as user input in various contexts comes at a significant performance and usability cost. Furthermore, system-hardening techniques such as ASLR have no effect on the attack as the attacker just maps (which is an unprivileged operation) the victim binary into its own address space. In principle we identified four conditions for an attack to succeed: 1) Disable Compiler and Linker Optimizations: For the concrete leakage of Chromium-based applications, disabling the linker optimizations would mitigate accurate keylogging. However, it is still possible to detect the activity of key groups as the keys are co-located in 4 different cache lines. Inter-keystroke timing attacks would also enable accurate keylogging as the cache activity can also be used for timing measurements between cache hits [95], [81], [61], [67], [89], [107], [72]. Moreover, removing these optimizations would bring back again overhead in the linking time [83]. 2) Golden device availability: All templating attacks require that the attacker is able to run the templating phase on a setup that is similar enough to the victim system [19], [79], [13], [40]. This is in principle not difficult to achieve as most desktop and laptop processors today are similar enough with respect to the cache side channel (i.e., 64byte cache lines and the availability of a flush instruction), that it is sufficient to have essentially any desktop or laptop processor available for the templating. It is slightly more challenging to obtain precisely the same software version and binary that is running on the target system. While software diversity [24] could be an avenue to break this link, it has not really found its way into practice yet. In practice, the vast majority of users runs binaries obtained from the official repositories or websites. While the idea of templating is decades old already [19], few works have looked at templating in the context of non-cryptographic leakage from software binaries, e.g., via caches [40], [107]. Since our layered approach, LBTA, makes the templating much faster, software diversity could be a possible mitigation to break this condition. Without a binary identical to the one the victim runs, i.e., due to software diversity, the attacker could not determine templates that work on the victim's system. 3) Secret-dependent execution: The side-channel leakage, e.g., which key was pressed, originates in differences in code and data accesses depending on the specific key value.
The state-of-the-art approach to secure cryptographic code is the linearization to a so-called constant-time implementation. Here, code and data accesses are always identical, regardless of the secret processed. For cryptographic algorithms this already comes at a non-negligible performance cost [21]. On an abstract level, the idea is to always run all the code and access all the data, e.g., in a square-andalways-multiply implementation [52]. However, for noncryptographic algorithms, always running all the code and accessing all the data is entirely infeasible. Domas [28] presented a compiler that linearizes the entire control flow to a sequence of mov instructions, effectively eliminating all secret-dependent branches, but with an enormous runtime overhead. Schwarzl et al. [91] further optimized this approach but still observe runtime overheads of factor 1000 and more, even for comparably simple applications. Borrello et al. [8] focused more on the protection of cryptographic implementations and still observe a runtime overhead of factor 3.17 to 5.07 on these relatively small examples. Hence, the problem of secret dependency on user input in large applications remains an open problem. 4) Side-channel observability: A practical limitation to the exploitation of secret-dependent execution is the sidechannel observability. While tools like CacheAudit [29] or CaSym [12], follow the cryptography-focused notion of constant time to consider an application leakage free, the practice for user input is more nuanced. For instance, distinguishing keys may be infeasible for an unprivileged attacker in practice when secret key-value-dependent execution exists but does not cross e.g., page or cache-line boundaries. In particlular, within a page, the hardware prefetcher will pose a substantial obstacle that introduces spurious cache activity on the target cache lines, foiling exploitation in practice [40]. The compiler could use this effect by grouping potentially secret-dependent accesses closer together or placing these strings in between frequently used code or data. We observed this effect in gcc where short strings are directly encoded into the instruction stream, or placed in physical proximity with other strings that are accessed based on a secret value. While specific patches can reduce the leakage in the cases we discovered, compilers could in general Office Software 0.99 % take side channels into account and employ side-channeladverse data placement, i.e., minimizing the number of cache lines a data structure is spread across. 5) Noise-resilience: Since user input cannot be arbitrarily triggered and repeated by the attacker millions of times, noise-resilience of the side channel is one condition for an attack on user input to succeed [89]. Hence, inducing noise, which is usually not recognized as a viable strategy for cryptographic operations, can provide strong practical security guarantees for user input which occurs at a low frequency and is not arbitrarily repeatable. In particular for modern systems, a low number of additional memory accesses for potentially secret dependent operations would come at a negligible performance cost while practically mitigating these attacks on user input. Furthermore, user annotations of potentially secret data may help minimizing the performance costs for this approach.

VII. DISCUSSION
LBTA is an effective technique to identify leakage in large binaries. As such, it cannot only used by attackers but is more interesting as a defensive technique revealing leakage already during the development process. While constant-time implementations have been analyzed for side channels being introduced by compilers [74], [101], [94], [11], developers should be aware that compiler and linker optimizations can lead to spatial distances in binaries enabling side-channel attacks on both hardware and software caches. We want to emphasize that string deduplication is not only related to native programs. Many languages like JavaScript, Java, PHP and Python perform string deduplication (under the term 'string interning') to reduce memory utilization. For instance, Java also offers the possibility of string deduplication (-XX:+UseStringDeduplication) during garbage collection which could lead to similar side effects.
We demonstrated that keystrokes in form input fields in Google Chrome can be detected using cache attacks on hardware and software caches. While Google Chrome is a valuable target, the dependency of many frameworks on the Chromium project, such as CEF and Electron, leads to a significantly higher impact as hundreds of browser-based desktop applications [30] are susceptible to accurate keylogging with our attack.
The templating phase runs in native code on an attackercontrolled system. While we also demonstrate the exploitation phase only in native code, we want to emphasize that browserbased attacks based on the same leakage are also possible. Using more advanced techniques like Prime+Probe in JavaScript and WebAssembly in the browser [104], [1], an attacker may then infer keystrokes from a browser tab, spying on another tab or an Electron app running on the victim's machine. The crucial challenge of such an attack would be to map the file offsets in the precomputed template to cache sets. However, LBTA is a generic technique that can be instantiated with various side channels, e.g., Prime+Probe that does not require any shared memory. Moreover, with techniques by Lipp et al. [61] and Gruss et al. [38], LBTA could be applied to Android as well.

VIII. CONCLUSION
We discovered that data deduplication and dead-stripping during compilation and linking facilitate side-channel leakage in compiled binaries. We show that this effect can even induce side-channel leakage in previously secure binaries, i.e., no secret-dependent accesses crossing a 64-byte boundary on the source level but on the binary level. The foundation to discover this attack was our extension to cache template attacks, called Layered Binary Templating Attacks, LBTA. LBTA is a scalable approach to templating that combines spatial information from multiple side channels. Using LBTA we scan binaries compiled with LLVM/clang, which applies deduplication and deadstripping by default. Our end-to-end attack is an unprivileged cache-based keylogger for all Chrome-based / Electron-based applications, including hundreds of security-critical apps, e.g., the popular Signal messenger app. While mitigation strategies exist, they come at a cost, and further research is necessary to overcome the open problem of side-channel attacks on user input. 0x14e7000 0x14e2000 0x14df000 0x14d2000 0x14c1000 0x14c0000 0x14be000 0x14bc000 0x14bb000 0x14ba000 0x14b9000 0x14b3000 0x14af000 0x14ab000 0x14aa000 0x14a9000 0x14a8000 0x14a2000 0x149b000 0x1494000 0x1492000 0x148f000 0x148e000 0x148c000 0x148b000 0x148a000 0x1521000 0x151b000 0x1513000 0x1510000 0x150d000 0x150b000 0x1509000 0x1508000 0x1506000 0x1505000 Fig. 9: Cache-hit ratio using a page cache attack for alphanumeric characters in Google Chrome.