# A theory of injection-based vulnerabilities in formal grammars

Eric Alata, Pierre-François Gimenez

► To cite this version:

Eric Alata, Pierre-François Gimenez. A theory of injection-based vulnerabilities in formal grammars. Theoretical Computer Science, 2025, 1057, pp.115554. 10.1016/j.tcs.2025.115554. hal-05379247

HAL Id: hal-05379247

https://hal.science/hal-05379247v1

Submitted on 24 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

<figure><img src="image_3.png" /></figure>

# A theory of injection-based vulnerabilities in formal grammars

Eric Alata ID a,*, Pierre-François Gimenez ID b

## ARTICLE INFO

Section Editor: Dr. Pinyan Lu

Handling Editor: Katie Harris

**Keywords:**

- Formal language

- Injection attack

- Web application

- Security

- Vulnerability

## ABSTRACT

Many systems are controlled via commands built upon user inputs. For systems that deal with structured commands, such as SQL queries, XML documents, or network messages, such commands are generally constructed in a “fill-in-the-blank” fashion: the user input is concatenated with a fixed part written by the developer (the template). However, the user input can be crafted to modify the command’s semantics intended by the developer and lead to the system’s malicious usages. Such an attack, called an injection-based attack, is considered one of the most severe threat to web applications. Solutions to prevent such vulnerabilities exist but are generally ad hoc and rely on the developer’s expertise and diligence. Our approach addresses these vulnerabilities from the formal language theory’s point of view. We formally define two new security properties. The first one, “intent-equivalence”, guarantees that a developer’s template cannot lead to malicious injections. The second one, “intent-security”, guarantees that every possible template is intent-equivalent, and therefore that the programming language itself is secure. We thoroughly analyze the decidability of these properties for the most common grammar classes. We conclude by highlighting the technical implications of these results for various settings and tools.

## 1. Introduction

The multiplication of new programming languages, software engineering frameworks, and tools has significantly shortened the Internet and web-based applications’ development cycles. The architectures of the applications generally share the same design pattern for accessing external resources: they rely on building one or several statements (generally called queries) for interpreters that perform the required actions on application resources. Such queries can be SQL queries for databases, shell system commands, XPath queries on XML documents, or a specific message format for a remote service on the Internet. Due to the low-level interaction between the application and the interpreter, such queries generally consist of a concatenated sequence of characters that may involve user-supplied data. More precisely, the developer generally writes a fill-in-the-blanks-type query, and user-supplied data is placed inside each “blank”.

However, user input is not always legitimate. There is a whole class of attacks that aim specifically at this widespread architecture: *injection-based attacks*. These attacks consist of submitting malicious inputs and building a malicious query whose semantics is different from what the developer had in mind. This vulnerability is not new: they have been known since 1998 when Phrack magazine described the first occurrence [1]. We can even retrospectively find it in phone phreaking during the 1950s. They can produce dramatic effects depending on the type of service, and their persistence vulnerability is generally attributed to a lack of developer awareness or bad practices [2]. In 2020, CWE (Common Weakness Enumeration) [3] listed SQL injection, OS-command injection,

<footnote>ª LAAS, Univ de Toulouse INSA, 7 avenue du colonel Roche, Toulouse, France</footnote>

<footnote>ᵇ Inria, IRISA, Univ. Rennes, France</footnote>

<footnote>* Corresponding author.</footnote>

<footnote>E-mail addresses: eric.alata@laas.fr (E. Alata), pierre-francois.gimenez@inria.fr (P.-F. Gimenez).</footnote>
and code injection among their 25 most dangerous software vulnerabilities. OWASP (Open Web Application Security Project) ranked injection as the most dangerous web application threat in 2017 [4] and as the third most dangerous one in 2021 [5]. Indeed, injections are ubiquitous as they affect nearly all programming languages families: a) query languages and network protocols like SQL, even with object-relational mapping (ORM), NoSQL, HTTP, SMTP and LDAP<fnref n="1" />, b) interpreted languages like JavaScript, HTML, CSS, python, Windows command line and Bash<fnref n="2" />, c) compiled languages such as Java and Go<fnref n="3" />, d) structured format as URL, JSON and XML<fnref n="4" />. This list is not exhaustive and gets longer and longer as new languages, protocols, and formats are developed and used.

Although many tools exist to identify and prevent injection-based attacks, they generally only treat the symptoms of these attacks, with ad hoc methods, and not the root cause of the vulnerability. Only a few articles were interested in the vulnerabilities embedded in the programming languages design itself, and this is the line of work we want to expand. By answering why all programming languages seem vulnerable to injection-based attacks, we seek to answer how such vulnerabilities could be detected and prevented at two steps: the design of a new language and its use by a developer. To this extent, this work relies on a new formalization of injection vulnerabilities. As suggested by [6], we consider that the developer had an intent in mind while writing the query. Any user input that this intent cannot explain is considered malicious. This new definition, particularly adapted to a theoretical analysis, led to several results on malicious injections depending on the query language grammar class. More precisely, we introduce two security properties: intent-equivalence and intent-security. A template is intent-equivalent to some intent if that intent can explain all injections, i.e., there are no malicious injections. A grammar is intent-secure if all its possible templates are intent-equivalent to some intent. In other words, an intent-secure grammar is not vulnerable to injection-based attacks. We analyze these properties for one or more blanks in the query and various grammar classes. We notably study regular, deterministic, and context-free grammars, along with some results concerning LR(k) grammars and visibly pushdown grammars. Furthermore, we characterize the set of malicious injections for various grammar classes.

Besides, our analysis also sheds new light with nuanced positions on several research questions on languages security:

* Q1: Does string concatenation necessarily lead to injection vulnerabilities?

* Q2: Could a skilled developer write only secure queries?

* Q3: Is a simpler language always more secure than a more complex one?

* Q4: Why do (nearly) all computer languages contain injection vulnerabilities?

This article is an extended version of [7]. Both articles build on the same definitions but have different goals. The goal of [7] is to propose design patterns for creating new, secure-by-design programming languages within a restricted family of LR languages. However, it does not help characterize the security of existing programming languages. This present article offers a detailed characterization of the injection problem and addresses other language classes beyond LR to answer this question.

The paper is structured as follows. Section 2 discusses related work and positions our main contributions. Then, Section 3 presents some fundamental background concepts of language theory. Our fundamental assumptions and their technical implications are discussed in Section 4. The intent-equivalence property is defined and studied in Section 5. The intent-security property is defined and analyzed in Section 6. Then, the characterization of the unintended injections is explored in Section 7. Finally, Section 8 summarizes our major results, presents their technical implications by providing part of the answers to the above questions, and discusses future directions.

## 2. Related work

### 2.1. Protection approaches

There are four main approaches to mitigate injection-based attacks: user input processing, intrusion detection, fuzzing, and static analysis.

User input processing is a broad category of run-time protection between the reception of the user input and the sending of the query to the interpreter. It includes filtering protection that modifies the user-provided data to avoid concatenation with malicious inputs. Typical filters are character escape (for example, `&` is often escaped into `&amp;` in HTML) and keyword filtering (for example, `<script>` tags are often removed entirely in HTML). Yet, the filtering effectiveness depends on the ability to identify malicious inputs while still allowing legitimate inputs. Another example is prepared statements, well-known for SQL queries, where the developer specifies what type of token the user input should be (an integer, a string, etc.). The prepared statement library checks the user input against the expected token type and handles the concatenation if possible. However, user input processing generally needs to be applied for each template. Attacks may still occur if the developer is unaware of injection-based attacks, does not use the user input processing properly due to a lack of skills or guidance, or simply forgets to protect one template.

Intrusion detection systems (IDS) [8] are generally deployed into the communication to analyze the network traffic and flag any suspicious activity. Such systems can either be signature-based or behavior-based. Signature-based IDS includes a list of signatures

<footnote n="1">¹ HTTP: CVE-2019-13143, SQL: CVE-2019-1010259 and CVE-2019-14900; NoSQL: CVE-2021-22911; SMTP: CVE-2017-9801; LDAP: CVE-2019-4297</footnote>

<footnote n="2">² JavaScript: CVE-2019-1020008; HTML: CVE-2019-1010113; CSS: CVE-2020-16254; python: CVE-2019-10633; Windows command line: CVE-2019-15599; Bash: CVE-2014-6271</footnote>

<footnote n="3">³ Java: CVE-2018-16621; Go: CVE-2020-28366</footnote>

<footnote n="4">⁴ URL: CVE-2022-0391, JSON: CVE-2018-14010; XML: CVE-2021-21025</footnote>
(written by experts or learned by machine learning) to recognize attacks. Behavior-based IDS know the system's normal behavior (either through specification or machine learning) and raise an alert whenever there is a significant deviation. However, signature-based IDS cannot detect new attacks, and behavior-based IDS generally produce too many false positives. They are usually commercial off-the-shelf software, i.e., ready-to-use and generic components. Therefore, they are effective in detecting common malicious injections (typically with a regular expression describing these attacks), but they may miss more exotic malicious injections that subtly change the semantics of queries.

Application testing and verification using fuzzing approaches is a simple way to identify vulnerabilities for applications with no or weak filtering [9]. These tools rely on sending inputs to the target architecture and detecting abnormal behaviors. In its most straightforward flavor, it consists of sending randomly generated inputs. This basic setting has been refined considering vulnerability scanners: they use smart algorithms to select candidate inputs most likely to detect vulnerabilities. Most of the time, they are based on a knowledge of how developers use interpreters. However, as illustrated in several experimental studies, these tools' detection coverage and efficiency still need to be significantly improved [10–13]. In addition, these approaches are very dependent on the level of expertise of their user. Thus, they have the same weakness as the IDS: they may miss malicious injections that subtly change the semantics of queries and require a good knowledge of the underlying language.

Static analysis methods are used to identify specific patterns corresponding to injection vulnerabilities [14,15]. These techniques are sometimes supported by formal methods that guarantee that only malicious injections are produced or, on the other hand, that no malicious injections are ignored during the analysis. Both cases require complete knowledge of the architecture, including the interpreter. These techniques are difficult to scale by considering all possible inputs: either they require a prohibitive execution time or generate an unrealistically large set of candidate inputs.

## 2.2. Tools

Recent surveys [16–19] related to injections confirm that most of the research in this area focuses on designing automated tools to address these vulnerabilities. The proposed tools are mainly based on run-time analysis [15,20] or propose technical countermeasures. It is noteworthy that formal methods-based analyses or research that studies injections from a purely theoretical perspective are not referenced in these surveys.

Research strongly focuses on the SQL language, limiting the scope of the proposed methods. Some works tackle injection attacks for other languages: mainly NoSQL [21,22] and HTML [23,24]. It is not easy to know to what extent these methods apply to other languages. Nevertheless, it is interesting to note that many approaches have taken advantage of machine learning to detect SQL injections in the last few years ([25] and [26]). For instance, SQLBlock [26] performs a learning process on the legitimate requests observed during the controlled execution of a PHP server. Then, it instruments the interface between PHP and SQL by inserting a plugin whose role is to make sure that the queries then generated comply with the form of the legitimate queries.

Besides, tainting and instrumentation of the code are still widely used [27–29], as well as comparison with an input signature base corresponding to injections. For example, the tool of [30] is inserted between the client and the server to compare user input with an SQL injection attack database using the Baeza-Yates-Gonnet algorithm. Likewise, the solution of [31] lies between the client and the server to analyze the packets exchanged and compare their content with a database of injection attack signatures. An alternative is AUTOGRAM [32], a fuzzer that relies on dynamic tainting to infer a context-free grammar of the input of a program. However, as shown later, such an input grammar is generally not context-free in the context of injections.

In [33], a framework is deployed in the cloud to analyze network traffic and detect SQL injection attacks using regular expressions. The choice of regular expressions is relevant to optimize the processing speed but at the expense of precision. A similar choice was made by [34–36] and [37].

In [38], authors observe that no solution can be easily transferred into the industry. They reviewed different tools to deal with SQL injection attacks (SQLProb [39], SQLrand [40], CANDID [6], WASP [29], etc.) to identify the ones that have the most potential for this transfer and concluded on WASP after an empirical study.

## 2.3. Language-theoretic approaches

Since injection-based attacks are based on textual data, many researchers applied results from the formal language theory. This theory studies the syntax of languages and their relations with automata (theoretical computing devices) and formal grammars (succinct descriptions of a language). This approach is notably pursued by the LangSec community that uses formal language theory to propose new tools and identify anti-patterns developers should avoid. However, even if several formal definitions of injection-based vulnerabilities have been proposed [6,20,41], no in-depth theoretical study has been carried out yet. Such a study could lead to new tools, e.g., to support query certification (guarantee that no malicious injection is possible), create new languages without these vulnerabilities, and automatically infer the language of malicious injections associated with a query. More generally, this theoretical analysis could lead to solutions that do not require (or require much less) expertise and would not be tied to a particular language or technology. This in-depth analysis based on formal language theory is the contribution of this paper.

We mentioned in the previous subsection that regular expressions had been used to detect SQL injection attacks. However, 20 years ago, the authors of [42] have shown that detection can require a more complex model than a regular expression. This last article comes from the language-theoretic security (LangSec) community that studies input attacks from a formal point of view. These attacks notably include buffer overflow and injection attacks. In 2005, [43] used formal language results, and notably undecidability theorems, to analyze input validation and propose multiple observations and advice to developers. In [44], the authors propose to
modelize input attack as a difference between the message a source wants to transmit and the message the destination receives. More precisely, they focus on an encoding function (used by the source to encode the message) and a decoding function (used by the destination to decode the encoded message). In this framework, an injection is defined as a message whose semantics is modified by the successive application of the encoder and the decoder. This framework led to several software, like McHammerCoder [45] or Nail [46].

The study of secure-by-design programming languages is not new. For example, the popular Rust language is memory-safe, protecting programs against memory-based vulnerabilities such as buffer overflow or pointers' use-after-free. The language Wyvern [47] proposes to embed in a single language SQL and HTML so the type system can verify if the user input matches the expected type. Sadly, this line of work did not transfer to the industry. Wyvern protection cannot extend over serialization, so it cannot prevent an injection if the concatenation is performed by another system. On the other hand, Wyvern do not require to modify the grammar while we do. Therefore, we consider our work to be complementary to Wyvern.

The contributions [2,48] of the LangSec community are complementary to our work. More precisely, this community tackles injection-based vulnerabilities from an end-to-end perspective, including the implementation issues, i.e., the difference between the target formal grammar and the parsing and unparsing software, with a particular focus on parsing flaws. For this reason, the contributions of the LangSec community generally don't rely solely on formal language theory and don't propose a formal definition nor study their theoretical implications. We consider that injection-based vulnerabilities ultimately stem from the formal grammar itself, and this is why we restrict our scope to its in-depth study.

## 2.4. Injection-based vulnerability formalization proposals

To the best of our knowledge, formal studies of injections have seldom been explored. The existing formal definitions are not used to characterize injections or answer the research questions raised in the introduction. Nevertheless, it is interesting to examine the scope and limitations of the proposed definitions.

The authors of [20] consider that a valid input from the user must correspond to structurally complete data (for example, a table name or a Boolean expression). They use this definition to add markers in SQL queries to delimit user inputs and test the validity of their structure. Although natural, this definition is too limited from our point of view. Indeed, for some applications, the user may be asked to provide data that is not structurally complete (for example, part of the name of a table instead of the full name or simply a Boolean operator instead of a Boolean expression).

In [6], authors focus on SQL and consider an injection to be a user input that does not belong to a finite list of symbols. Knowing the SQL query to protect and the list of legitimate symbols, they can build a list of legitimate abstract syntax trees. During the execution, the concatenation with the user data must lead to one of these abstract syntax trees considered legitimate. This definition is also debatable because the legitimate user inputs can be infinite (for example, if they correspond to a Boolean expression, given that the set of Boolean expressions is infinite). Besides, in some cases, an injection may change how the query is parsed while preserving the syntax tree's overall structure.

The last formalization we mention is not dedicated to injection-based attacks but should encompass any computer attacks. This formal framework for security uses “weird machines”, a concept used by exploit practitioners and described in [49]. In this framework, what the developer intends to implement is modelized as an “intended finite state machine” (IFSM). It may differ from the actual implementation, modelized by another finite state machine that may have additional states (called “weird states”) with no equivalent states in the IFSM. This framework encompasses a large number of vulnerabilities, both hardware and software. However, we argue that this framework is not adapted to injection vulnerabilities. Injection attacks typically happen when two systems interact: an interpreter that processes queries and a client that sends queries. Two disjoint teams generally develop these systems. However, in injection attacks, both systems behave accordingly to the intent of their developers. In the case of an SQL injection, for example, the interpreter receives a malicious query. Since an interpreter's purpose is to execute queries, an SQL attack can happen even if the interpreter has no weird state (i.e., is safe in the weird machine framework). It is also the case for the client. In most cases, the only difference between a legitimate and a malicious user input is in the data manipulated (generally as string). A malicious user input doesn't need to change the flow of the program (i.e., the path in the intended finite state machine). For example, an attack could affect only the interpreter system with an injected “DROP table” instruction that deletes part of a database with no (immediate) effect on the client. Injection attacks are challenging to study because they may happen at the interface of two systems with no weird states.

# 3. Background

This section aims at providing a brief presentation of some notions of formal language and grammar used in the next sections.

## 3.1. Formal grammars

A formal grammar $G = (N, T, R, S)$ consists of four elements. $T$ is a finite set of terminal symbols, called the alphabet. $N$ is a finite set of nonterminal symbols, disjoint from $T$. We will denote $\Delta = N \cup T$ the set of all symbols. The elements of $\Delta^*$ are sentential forms, and the elements of $T^*$ are words, where $^*$ represents the Kleene star operation. The empty sentential form is denoted $\epsilon$. The length of a sentential form $\alpha$, denoted $|\alpha|$, is the number of symbols it is composed of (so $\alpha \in \Delta^{|\alpha|}$).

$R$ is a finite set of rules (also called productions). A production is an expression of the form $\alpha \to \beta$, where $\alpha \in \Delta^+ - N^+$ (i.e., $\alpha$ contains at least one terminal), $\beta \in \Delta^*$. Finally, $S$ is a symbol of $N$ called the axiom.
<table><caption>**Table 1**
Chomsky hierarchy.</caption><thead><tr><th>Type 0</th><th>Any grammar</th><th>no restriction on the rules form</th></tr></thead><tbody><tr><td>Type 1</td><td>Context-sensitive grammar</td><td>rules of the form: αAβ → αγβ with A ∈ N, α, β ∈ N*, γ ∈ Δ<sup>+</sup></td></tr><tr><td>Type 2</td><td>Context-free grammar</td><td>rules of the form: A → β with A ∈ N, β ∈ Δ<sup>+</sup></td></tr><tr><td>Type 3</td><td>Regular grammar</td><td>rules of the form: A → aB, A → a or A → e with A, B ∈ N, a ∈ T</td></tr></tbody></table>

In the following, we generally use uppercase Latin letters at the start of the alphabet (A, B, ...) for nonterminals, lowercase Latin letters at the start of the alphabet (a, b, ...) for terminals, lowercase Latin letters at the end of the alphabet (u, v, ...) for words and Greek letters (α, β, ...) for sentential forms.

Let $r = α → β$ be a rule of G. A sentential form $ω_1αω_2$ directly derives $ω_1βω_2$ by applying $r$, written $ω_1αω_2 ⇒_G ω_1βω_2$, for any $ω_1, ω_2 ∈ Δ^*$. If $ω_1, ω_2, ..., ω_n$ are sentential forms such that $ω_1 ⇒_G ω_2 ⇒_G ... ⇒_G ω_n$, then $ω_1$ derives $ω_n$, written $ω_1 ⇒_G^* ω_n$ ($⇒_G^*$ is the reflexive transitive closure of $⇒_G$). Since $⇒_G^*$ is reflexive, every sentential form $α ∈ Δ^*$ derives itself: $α ⇒_G^* α$. For simplicity, we will omit the subscript G when it is understood. A word $w$ is *derivable* from the grammar if there exists a sequence of rules that leads to this word when applied from the axiom $S$, i.e. $S ⇒_G^* w$. A nonterminal $A$ is reachable from the axiom if there exists $α, β ∈ Δ^*$ such that $S ⇒_G^* αAβ$. The notation $ω ≠_G^* γ$ denotes that $γ$ is not derivable from $ω$ by any sequence of derivation steps.

The language generated by the grammar is the set of derivable words from its axiom and is noted $L(G)$.

For a given sentential form $w = x_1x_2...x_m$, where $m ∈ N$ and $x_i ∈ Δ$ for $i = 1, 2... m$, the reversal of $w$ is the word $w^r = x_mx_{m-1}...x_1$. We extend this notation to language: $L^r = \{w^r | w ∈ L\}$.

In the following, we will use the notion of *quotient of languages*, that can be defined as follows. If $A$ and $B$ are languages (i.e., subsets of $T^*$), the left quotient of $A$ by $B$, written $B \setminus A$, is the set $\{v \in T^* | \exists u \in T^* : uv \in A \land u \in B\}$. Similarly, the right quotient $A/B$ is $\{u \in T^* | \exists v \in T^* : uv \in A \land v \in B\}$. We will denote $p \setminus A$ the left quotient of $A$ by the language containing solely the word $p \in T^*$ and $A/s$ the right quotient of $A$ by the language containing solely the word $s \in T^*$.

We will denote tuples in boldface. For example: $t = (t_1, ..., t_m)$.

## 3.2. Grammar classes

The hierarchy of Noam Chomsky classifies grammars into several types [50], according to the restrictions on the form of the rules. This classification is briefly described in Table 1. A language $L$ is said to be of type $t$ whenever there exists a type-$t$ grammar $G$ such that $L = L(G)$. Many decision problems about formal languages depend on the language type [51–53]. In this work, we *limit the scope of our research to injections in context-free languages*, where the left-hand part of each rule consists of one non-terminal.

For context-free languages, one can represent a derivation in the form of a rooted tree, called *derivation tree*. Each node is labelled by an element of $Δ$; the root is labelled by the axiom $S$, each internal node is labelled by a nonterminal and each leaf is labelled by a terminal. A context-free grammar is said *ambiguous* if there exists at least one word with multiple derivation trees, and *unambiguous* if such a word does not exist.

In addition to these classic grammar types, we will be interested in some other classes: deterministic context-free grammars, LR($k$), LR(0) and LL(1) grammars. Deterministic context-free grammars [54] are derived from deterministic pushdown automata. They form a proper subset of context-free grammars and are widely used because they can be parsed in linear time.

A subset of deterministic context-free grammars are LR($k$) grammars [55] (LR stands for “left-to-right, rightmost derivation”) for any $k \ge 1$. LR($k$) grammar definition from [56] (Def 2.1) relies on the concept of rightmost derivation. A rightmost derivation is a derivation in which at any derivation step the rightmost nonterminal is rewritten. Let us denote $⇒_R$ the rightmost derivation and $⇒_R^*$ its reflexive transitive closure. Let us also denote $^{(k)}w$ the prefix of $w$ with length $min(|w|, k)$. The definition of an LR($k$) grammar is as follow: let $G = (N, T, R, S)$ be a grammar such that $S \Rightarrow_R^+ S$ and let $w, w', x \in T^*$, $γ, α, α', β, β' \in Δ^*$, $A, A' \in N$. $G$ is said to be LR($k$) if the following implication is true: if $S ⇒_R^* αAw ⇒_R αβw = γw$, $S ⇒_R^* α'A'x ⇒_R α'β'x = γw'$ and $^{(k)}w = ^{(k)}w'$, then $A = A'$, $β = β'$, $|αβ| = |α'β'|$. This property makes them effectively parsed by an LR parser [55]. All LR($k$) for $k \ge 1$ describe the same set of languages: the deterministic context-free languages. A strict subset of LR($k$) grammars is the set of LR(0) grammars: they can be parsed without any lookahead.

Visibly pushdown languages are a strict subset of deterministic languages with many closures properties and decidable problems [57]. They rely on a partition of the alphabet in three sets: calls, returns, and local symbols. Each set can only affect the stack of the automata in some way.

Finally, linear grammars [58] are grammars where the right-hand part of the rules can contain at most one non-terminal. They are context-free grammars but may be non-deterministic. For example, the set $\{ww^r | w \in T^*\}$ is not deterministic [52] but can be easily expressed with the linear grammar $(\{S\}, T, \{S \to tSt | t \in T\} \cup \{S \to e\}, S)$.

Since we will be most interested in grammars, we differentiate the set of grammars from the set of languages. See Table 2 for a list of abbreviations used in this article. A summary of the inclusion properties of these languages is presented in Fig. 1.

Table 3 summarizes the closures and non-closures properties of operations for classic grammar classes [52,57,58]. These operations are classical operations on sets (union, complement, intersection) and strings (concatenation, also called product). Homomorphisms are letter-to-string functions (i.e., $T \to T^*$). They are extended to string-to-string functions in a morphic way: $h(ε) = ε$, $h(uv) = h(u)h(v)$ for all strings $u, v \in T^*$.
<table><caption>**Table 2**
Abbreviation of some languages and grammars classes.</caption><thead><tr><td>Name</td><td>Grammar class</td><td>Language class</td></tr></thead><tbody><tr><td>Regular</td><td>REGG</td><td>REGL</td></tr><tr><td>Visibly pushdown</td><td>VPG</td><td>VPL</td></tr><tr><td>Deterministic context-free</td><td>DCFG</td><td>DCFL</td></tr><tr><td>Linear</td><td>LinG</td><td>LinL</td></tr><tr><td>Context-free</td><td>CFG</td><td>CFL</td></tr></tbody></table>

<figure><img src="image_4.png" /><figcaption>**Fig. 1.** An arrow from class A to B indicates that A is a strict subset of B.</figcaption></figure>

<table><caption>**Table 3**
Closure (symbol ✓) and non-closures (symbol ✗) of various languages classes with respect to classic operations.</caption><thead><tr><td>Operation</td><td>REGL</td><td>LL(1)</td><td>LR(0)</td><td>VPL</td><td>DCFL</td><td>LinL</td><td>CFL</td></tr></thead><tbody><tr><td>Concatenation</td><td>✓</td><td>✗</td><td>✓</td><td>✓</td><td>✗</td><td>✗</td><td>✓</td></tr><tr><td>Union</td><td>✓</td><td>✗</td><td>✗</td><td>✓</td><td>✗</td><td>✓</td><td>✓</td></tr><tr><td>Complement</td><td>✓</td><td>✗</td><td>✗</td><td>✓</td><td>✓</td><td>✗</td><td>✗</td></tr><tr><td>Intersection with regular set</td><td>✓</td><td>✗</td><td>✗</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td></tr><tr><td>Inverse homomorphism</td><td>✓</td><td>✗</td><td>✗</td><td>✗</td><td>✓</td><td>✓</td><td>✓</td></tr></tbody></table>

<table><caption>**Table 4**
Decidability (D) and undecidability (U) of various problems on languages classes.</caption><thead><tr><td>Problem</td><td>REGL</td><td>LL(1)</td><td>LR(0)</td><td>VPL</td><td>DCFL</td><td>LinL</td><td>CFL</td></tr></thead><tbody><tr><td>Membership (w ∈ L?)</td><td>D</td><td>D</td><td>D</td><td>D</td><td>D</td><td>D</td><td>D</td></tr><tr><td>Equivalence (L<sub>1</sub> = L<sub>2</sub>?)</td><td>D</td><td>D</td><td>D</td><td>D</td><td>D</td><td>U</td><td>U</td></tr><tr><td>Inclusion (L<sub>1</sub> ⊆ L<sub>2</sub>?)</td><td>D</td><td>U</td><td>U</td><td>D</td><td>U</td><td>U</td><td>U</td></tr><tr><td>Emptiness (L = Ø?)</td><td>D</td><td>D</td><td>D</td><td>D</td><td>D</td><td>D</td><td>D</td></tr></tbody></table>

Table 4 summarizes the decidability of various problems for the same grammar classes [59,60]: membership, equivalence, inclusion and emptiness.

## 4. Motivation for malicious injections modelization

Injections vulnerabilities typically stem from the integration of untrusted user input to build queries. In this paper, we use the term *query* to denote the complete string that includes the part written by the developer and the part that stems from the user input. We use the term *template* to denote the set of strings the developer writes to construct their query by concatenation. The term *blank* denotes a place in a template in which the user input can be inserted by concatenation. A template can contain either one blank (for instance, a search form) or multiple blanks (for instance, an authentication form). The data injected by users in the template is called an *injection*. We find the term “user input” inappropriate because the injection may not come directly from a human user (as it can be the case in second-order injection attacks). Besides, the user input may be modified (typically escaped or truncated) before being included in the template. Remark that, with this definition, an injection is not necessarily malicious: legitimate injections exist as well and are expected.

Let us illustrate new concepts we introduce with the LDAP language, because it has a simple grammar, is widely used and can be targeted by injection-based attacks. A simplified grammar $G_{LDAP}$ can be expressed with the following rules:

$$S \to (\!S) \quad S \to (s=s) \quad S \to (\&L) \quad S \to (|L) \quad L \to S \quad L \to LS$$

where *S* is the axiom, *L* is a non-terminal denoting a list, and *s* is a token that can match any alphanumerical string. Semantically, *|* is the negation, & is the logical conjunction (“AND”) and | is the logical disjunction (“OR”). This grammar is LR(0) and is not regular.
For the sake of illustration, assume the developer maintains directory information services that can be searched with LDAP, a widely used protocol, especially for user authentication. They design the following template to check if a username and a password exist:

$$ (&(uid=___) (passwd=___)) $$

This template has two blanks, denoted `___`, where user inputs can be injected. The developer expect the user to input one string for each blank so, intuitively, any user input that is not a string should be considered malicious. Sometimes, the developer can expect a more complex user input, like a list of comparisons, or a Boolean formula. We assume that legitimate injections comply with the developer's intent which can be modelized as a symbol of the grammar, or a sequence of symbols. In the previous template, the intent of the developer can be modelized as the terminal s.

We justify this choice as follow. A malicious injection is an injection that modifies the semantics of the query. We cannot use this definition as formal language theory does not model semantics. However, the semantics is handled by parsers that heavily relies on a grammar. Even though there is an infinity of grammars that describe any language, there is generally one grammar of reference for every programming language. Such grammar has not been chosen at random: it is optimized to be understandable by the human (for example, the name of nonterminals generally conveys some semantics about its role in the grammar) and to facilitate the production of the semantics by the parser (generally used by a compiler or an interpreter). For these reasons, we make the reasonable assumption that the syntactic analysis by the grammar of reference of a language strongly correlates the sentence's semantics.

Classic injection attacks clearly illustrate that they must indeed modify the order and the types of the tokens of the queries drastically to modify the way the sentence is parsed and thus its semantics. When a developer writes a template, they have some intent about the user input: a name, a number, or a more complex structure such as a Boolean expression for a condition. Our fundamental assumption is that these intents correspond to symbols or sequences of symbols of the grammar of reference of that language. We consider that legitimate injections respect the intent while malicious injections don't. These terms are formally defined in the next sections.

This article aims at providing results, answers, and advice for these various application cases.

# 5. Intent-equivalence

In this section, we define and study the intent-equivalence property.

## 5.1. Formal definition of the intent-equivalence

For the sake of simplicity, we will first restrict our definition to templates with a single blank. The definitions will be extended to templates with multiple blanks at the end of this subsection. In the single-blank setting, a template p `___` s can be described as a prefix p and a suffix s. In the following, every definition are given with respect to a grammar G = (N, T, R, S).

Let us begin by defining the set of injections that can be used in some template. This definition is straightforward: it is the set of factors that lead to a valid (syntactically correct) word when inserted into the template.

**Definition 5.1** (Injections of L for a template (p, s)). Let L be a formal language and p, s ∈ T*. We define the language of injections of L associated to a template (p, s) as the language defined by:

$$ F(L, (p, s)) = \{w \in T^* | \text{pws} \in L\} = p \setminus L / s $$

Among these injections, there may be legitimate and malicious ones. As proposed in the previous section, we formalize the legitimate injections by the set of words that can be derived from a sentential form we call the intent. If the intent of the developer is some i ∈ Δ⁺, then they expect a user input that can be derived from i. Therefore, we call the expected injections for intent i the injections that can be derived from i.

**Definition 5.2** (Expected injections of G for intent i). Let i ∈ Δ⁺. The language of expected injections of G for intent i, noted E(G, i), is defined as:

$$ E(G, i) = \{w \in T^* | i \Rightarrow^* w\} $$

**Example 5.3.** Consider the following LDAP template t: (`&(uid=___)(passwd=1234)`) Let us assume the intent of the developer is the terminal s, i.e., the user is expected to enter a string. Since s is a terminal, the only expected injection is s, i.e., E(G<sub>LDAP</sub>, s) = {s}. However, the injection foo) (loc=bar lead to the syntactically valid query: (`&(uid=foo)(loc=bar)(passwd=1234)`) So foo) (loc=bar ∈ F(L(G<sub>LDAP</sub>), i) and foo) (loc=bar /∈ E(G<sub>LDAP</sub>, s). Therefore, this template can accept injections that do not comply with the intent of the developer: this template is therefore vulnerable.

Notice that the set of expected injections of a regular (resp. context-free) grammar G is also a regular (resp. context-free) language. So this set is generally as easy to manipulate as G. So, given an intent, it is easy to verify whether or not some injection is compatible with it, i.e., if the injection is a member of the expected injections associated to that intent.

Remark that this definition of expected injections is adapted to context-free grammars but not to context-sensitive grammars. Indeed, in context-sensitive grammars, the strings consistent with an intent could depend on the context (i.e., the template). For this
reason, we limit our study to context-free languages. We do not consider this limitation of our framework as very restrictive, since almost all programming languages have context-free grammars<fnref n="5" />.

**Proposition 5.4.** Let $G$ be a context-free grammar, $t \in \Delta^+$ and $w \in T^*$. It is decidable whether or not $w \in E(G, t)$.

**Proof.** Let $G' = (N \cup \{S'\}, T, R \cup \{S' \to t\}, S')$ where $S'$ is a new nonterminal. This grammar is context-free and recognizes the language $L(G') = \{w | t \Rightarrow_G^* w\} = E(G, t)$. The membership problem for context-free grammar is decidable [61]. Thus, it is decidable if $w \in E(G, t)$. □

If $t$ is a sequence of terminals, the only sentential form $w$ for which $t \Rightarrow^* w$ is $t$ itself and therefore $E(G, t) = \{t\}$. Such intent may seem useless because then the developer would expect only one possible injection, removing all information gained from the user input. However, in general, the terminals of real-world grammars are tokens whose recognition is handled by the lexer, and tokens like “string” or “number” entail multiple possibilities for user inputs. So, most intent are in fact terminals.

A template is secure if the set of all injections is explained by at least one intent $t$ that could appear in that sentence. In that case, we say that the template is *intent-equivalent to* $t$.

**Definition 5.5 (Intent-equivalence to an intent).** Let $G$ be a formal grammar and $p, s \in T^*$ and $t \in \Delta^+$. The template $(p, s)$ is *intent-equivalent to* $t$ if:

$$S \Rightarrow^* p \text{ts} \quad \text{and} \quad F(L(G), (p, s)) = E(G, t)$$

**Remark 5.6.** To prove that $(p, s)$ is intent-equivalent to $t$, it suffices to show that $S \Rightarrow^* p \text{ts}$ and $F(L(G), (p, s)) \subseteq E(G, t)$, as $S \Rightarrow^* p \text{ts}$ implies $E(G, t) \subseteq F(L(G), (p, s))$.

**Example 5.7.** Let us consider the grammar $G = (\{a, b, c, d\}, \{S\}, R, S)$ where $R = \{S \to aSb; S \to cd\}$, and the following template: `aa--cdbbb`. Here, the only injection that lead to a syntactically correct sentence is “aa”. Therefore, this template is intent-equivalent to “a”.

**Remark 5.8.** $S \Rightarrow^* \alpha$ ($\alpha \in \Sigma^*$) is always decidable because $G$ is context-free. Indeed, one can create a grammar $G' = (N, T \cup \{t_A | A \in N\}, R \cup \{A \to t_A | A \in N\}, S)$ that creates a new terminal for each non-terminal, so each sentential form of $L(G)$ can be mapped to a word of $L(G')$ with the following bijective homomorphism $h$:

$$h(a) = \begin{cases} t_a & \text{if } a \in N \\ a & \text{if } a \in T \end{cases}$$

By construction, $S \Rightarrow_G^* \alpha$ if and only if $S \Rightarrow_{G'}^* h(\alpha)$, which is decidable because $G'$ is context-free. In particular $S \Rightarrow_G^* p \text{ts}$ if and only if $S \Rightarrow_{G'}^* h(p \text{ts})$.

In various cases, a template can include multiple blanks. A classic example is the template associated to a login page that has generally a blank for the username and another for the password. We generalize the previous definitions for templates with $m$ blanks and intentions that are tuples. As a reminder, we denote tuples in boldface.

A template is a sequence of terminals with some blanks: $t_1 \to t_2 \to t_3 \to \dots \to t_m \to t_{m+1}$. We impose the presence of at least one terminal between two blanks; without this constraint, one blank could be interpreted as several adjacent blanks.

**Definition 5.9 (Template with $m$ blanks).** Let $m \ge 1$. A template with $m$ blanks is a sequence $t = (t_1, \dots, t_{m+1}) \in T^* \times (T^+)^{m-1} \times T^*$.

Given a template with $m$ blanks and $m$ injections, we define the fill-in-the-blanks operator that creates the concatenation of the template with the injections.

**Definition 5.10 (Fill-in-the-blanks operator).** Let $m \ge 1$. We define the fill-in-the-blanks operator $\odot$ as:

$$\odot : (T^* \times (T^+)^{m-1} \times T^*) \times (T^*)^m \to T^* \\ (t_1, \dots, t_{m+1}), (w_1, \dots, w_m) \mapsto t_1 w_1 t_2 w_2 \dots w_m t_{m+1}$$

We will use the infix notation (e.g. $t \odot w$, read “t filled with w”) for this operator.

Let us expand the previous Definitions (5.1, 5.2, and 5.5) to templates with $m$ blanks.

**Definition 5.11 (Injections of $L$ for a template $t$).** Let $L$ be a formal language, $m \ge 1$ and $t \in T^* \times (T^+)^{m-1} \times T^*$. We define the language of injections of $L$ associated to a template $t$ as the language defined by:

$$F(L, t) = \{w \in (T^*)^m \mid t \odot w \in L\}$$

**Definition 5.12 (Expected injections of $G$ for intents $t$).** Let $G$ be a formal grammar, $m \ge 1$ and $t = (t_1, t_2, \dots, t_m) \in (\Delta^+)^m$. The language of expected injections of $G$ for intents $t$, noted $E(G, t)$, is defined as:

$$E(G, t) = E(G, t_1) \times \dots \times E(G, t_m)$$

**Definition 5.13 (Intent-equivalence of a template to an intent).** Let $G$ be a formal grammar, $m \ge 1$, $t \in T^* \times (T^+)^{m-1} \times T^*$ and $t \in (\Delta^+)^m$. The template $t$ is *intent-equivalent to* $t$ if:

$$S \Rightarrow^* t \odot t \quad \text{and} \quad F(L(G), t) = E(G, t)$$

<footnote n="5">⁵ See Antlr Project (https://github.com/antlr/grammars-v4)</footnote>
## 5.2. Decidability of intent-equivalence

In this subsection, we are interested in the decidability of the intent-equivalence of a template t with m blanks to some fixed intent t for various classes of grammar. This problem mainly concerns the static analysis of the source code, where we have access to the template. The first class we study is that of regular grammars.

**Theorem 5.14.** Let $G = (N, T, R, S)$ be a regular grammar, $m \ge 1$, t a template with m blanks and $t \in (\Delta^+)^m$. It is decidable whether t is intent-equivalent to t.

**Proof.** To decide the intent-equivalence, we have to prove that $F(L,t) = E(G,t)$. These two sets contain m-tuples and, therefore, are not languages. To apply results from language theory, we transform these tuples into words with the injective function $f_t$ that relies on new symbols $\#_i, \overline{\#}_i$, for $m \ge i \ge 1$ and defined as follow:

$$f_t(\mathbf{w}) = t \odot (\#_1 w_1 \overline{\#}_1, \#_2 w_2 \overline{\#}_2, \dots, \#_m w_m \overline{\#}_m)$$

If $f_t(F(L,t)) = \{f_t(\mathbf{w}) | \mathbf{w} \in F(L,t)\}$ is equal to $f_t(E(G,t)) = \{f_t(\mathbf{w}) | \mathbf{w} \in E(G,t)\}$ then $F(L,t) = E(G,t)$ due to $f_t$ being injective.

Let us first construct the set $f_t(F(L,t))$ with the languages $L_1$ and $L_2$. $L_1$ is the language L whose each word have been doped with the new symbols $\#_i, \overline{\#}_i$ for $m \ge i \ge 1$. Consider the following homomorphism h:

$$h(a) = \begin{cases} \epsilon & \text{if } a = \#_i \text{ or } a = \overline{\#}_i \text{ for some } m \ge i \ge 1 \\ a & \text{if } a \in T \end{cases}$$

This homomorphism removes the symbol $\#_i$ and $\overline{\#}_i$, so its inverse adds these symbols and $L_1 = h^{-1}(L)$. Since regular languages are closed under inverse homomorphisms, $L_1$ is regular. Remark that $f_t(\mathbf{w}) \in L_1$ if and only if $t \odot w \in L$.

$L_2$ is the set of templates completed with any factors where each factor is surrounded by $\#_i$ and $\overline{\#}_i$. Remark that, with a slight abuse of notation, $L_2 = t \odot (\#_1 T \overline{\#}_1, \#_2 T \overline{\#}_2, \dots, \#_m T \overline{\#}_m)$. As a finite concatenation of regular languages, this language is regular. Furthermore, it does not depend on the language L. We will now prove that $f_t(F(L,t)) = L_1 \cap L_2$.

⊆: Let $w \in F(L,t)$. Remark that $L_2 = \{f_t(\mathbf{w}) | \mathbf{w} \in (T^*)^m\}$ so $f_t(\mathbf{w}) \in L_2$. Besides, $t \odot w \in L$, so $f_t(\mathbf{w}) \in L_1$. So $f_t(F(L,t)) \subseteq L_1 \cap L_2$.

≥: Let $w \in L_1 \cap L_2$. Since $L_2 = \{f_t(\mathbf{w}) | \mathbf{w} \in (T^*)^m\}$, there exists $w' \in (T^*)^m$ such that $w = f_t(w')$. Since $f_t(w') \in L_1$, we know that $t \odot w' \in L$, so $w' \in F(L,t)$. So $L_1 \cap L_2 \subseteq f_t(F(L,t))$.

Finally, $f_t(F(L,t)) = L_1 \cap L_2$. Since $L_1$ and $L_2$ are regular, the set $f_t(F(L,t))$ is regular. Besides, $f_t(E(G,t)) = \{t \odot (\#_1 w_1 \overline{\#}_1, \#_2 w_2 \overline{\#}_2, \dots, \#_m w_m \overline{\#}_m) | \forall i, w_i \in E(G, t_i)\}$. Since every language $E(G, t_i)$ is regular, $f_t(E(G,t))$ is regular.

So the template t is intent-equivalent to t if and only if $f_t(F(L,t)) = f_t(E(G,t))$. Since both languages are regular, this is decidable (by Theorem 3.12 from [52]). □

This result should not be surprising as most problems are decidable for regular grammars. To expand this result to deterministic language, we would need to compare the languages of expected injections $E(G,t)$ with the language of injections. However, this may not be easy. Consider the case with one blank, where t = (p, s). In that case, $F(L, (p, s)) = p \setminus L(G)/s$. But while $p \setminus L(G)/s$ is necessarily deterministic, we don't know whether $E(G,t)$ is deterministic or not in the general case. Nonetheless, we prove in the following lemma that for an intent of length 1 ($t \in \Delta$), if G is an LR(k) grammar then $E(G,t)$ is deterministic.

**Lemma 5.15.** Let $k \in \mathbb{N}$ and $G = (N, T, R, S)$ be an LR(k) grammar. Then, for any $A \in \Delta$ reachable from S, $G' = (N, T, R, A)$ is a LR(k) grammar.

**Proof.** This proof relies on the definition of LR(k) grammars described in Section 3.2.

The case where A is a terminal is trivial, as in this case $E(G, A) = \{A\}$ is finite. In the following, we assume that A is a nonterminal. Since A is reachable from S, there exist $\delta \in \Delta^*$ and $w \in T^*$ such that $S \Rightarrow_R^* \delta A w$. Let $\alpha, \gamma \in \Delta^*, w_1, w_2, w_3 \in T^*$ such that:

$$A \Rightarrow_R^* \alpha B w_2 \Rightarrow_R \alpha \beta w_2$$

$$A \Rightarrow_R^* \gamma C w_1 \Rightarrow_R \alpha \beta w_3$$

$$(k) w_2 = (k) w_3$$

$G'$ is LR(k) if $\alpha = \gamma$, $B = C$ and $w_1 = w_3$. Since $S \Rightarrow_R^* \delta A w$:

$$S \Rightarrow_R^* \delta A w \Rightarrow_R^* \delta \alpha B w_2 w \Rightarrow_R^* \delta \alpha \beta w_2 w$$

$$S \Rightarrow_R^* \delta A w \Rightarrow_R^* \delta \gamma C w_1 w \Rightarrow_R^* \delta \alpha \beta w_3 w$$

Remark that if $(k) w_2 = (k) w_3$ then $(k) (w_2 w) = (k) (w_3 w)$. We can use our hypothesis that G is LR(k) and conclude that $\delta \alpha = \delta \gamma$, $B = C$, $w_1 w = w_3 w$. Hence $\alpha = \gamma$ and $w_1 = w_3$, so $G'$ is LR(k). □

This lemma allows us to adapt the proof of Theorem 5.14 and to conclude the decidability of the intent-equivalence for LR(k) grammar when the intent length is 1.

**Theorem 5.16.** Let G be an LR(k) grammar, $m \ge 1$, t a template with m blanks and $t \in (\Delta^+)^m$ (so $|t_i| = 1$ for all i). It is decidable whether t is intent-equivalent to t.
**Proof.** The proof is similar to the proof of **Theorem 5.14**. Deterministic languages are closed by inverse homomorphism, so $L_1$ is deterministic. They are also closed by intersection with a regular language, so $L_1 \cap L_2$ is deterministic ($L_2$ doesn't depend on $L$ and is always regular). Because each $E(G, t_i)$ is LR($k$) (due to **Lemma 5.15**) and because $f_i(F(L, t))$ is a marked concatenation of LR($k$) languages, $f_i(F(L, t))$ is deterministic [56]. So $F(L, t)$ and $E(G, t)$ are deterministic. Finally, the equivalence of deterministic languages is decidable [62]. We can conclude that it is decidable whether $t$ is intent-equivalent to $i$. $\square$

This theorem is limited to $|t_i| = 1$ (i.e., to intent length equal to 1) because, otherwise, $E(G, t_i)$ may not be LR($k$). However, LR(0) grammars are closed by concatenation, so we obtain the following result:

**Theorem 5.17.** Let $G$ be an LR(0) grammar, $m \ge 1$, $t$ a template with $m$ blanks and $t \in (\Delta^+)^m$ (no constraint on the size of $t_i$). It is decidable whether $t$ is intent-equivalent to $i$. $\square$

**Proof.** The proof is similar to the proof of **Theorem 5.16**. Denote $t_i = t_{i,1}t_{i,2} \dots t_{i,k}$. We can decompose $E(G, t_i)$ in the following way: $E(G, t_i) = E(G, t_{i,1}) \cdot E(G, t_{i,2}) \cdot \dots \cdot E(G, t_{i,k})$. Due to previous lemma, each set $E(G, t_{i,j})$ (for $1 \le j \le k$) is an LR(0) language. Since the languages LR(0) are closed by product [56], $E(G, t_i)$ is an LR(0) language. The rest of the proof is similar. $\square$

**Example 5.18.** $G_{LDAP}$ is LR(0) so the intent-equivalence of any of its templates could be automatically assessed. For example: $(! (uid=foo) —)$ is intent-equivalent to $|$ and $(\&(uid= —)(passwd=1234))$ is not intent-equivalent to $s$ (as discussed in **Example 5.3**).

The same result can be obtained for visibly pushdown grammars, for about the same reasons.

**Theorem 5.19.** Let $G$ be a visibly pushdown grammar, $m \ge 1$, $t$ a template with $m$ blanks and $t \in (\Delta^+)^m$ (no constraint on the size of $t_i$). It is decidable whether $t$ is intent-equivalent to $i$. $\square$

**Proof.** Let $G = (N, T, R, S)$ a visibly pushdown grammar. The proof is similar to the previous one. Denote $t_i = t_{i,1}t_{i,2} \dots t_{i,k}$. We can decompose $E(G, t_i)$ in the following way: $E(G, t_i) = E(G, t_{i,1}) \cdot E(G, t_{i,2}) \cdot \dots \cdot E(G, t_{i,k})$. Each set $E(G, t_{i,j})$ is either described by the grammar $G = (N, T, R, t_{i,j})$ if $t_{i,j}$ is a nonterminal, or is finite if $t_{i,j}$ is a terminal. In both case, $E(G, t_{i,j})$ is visibly pushdown. Since the visibly pushdown languages are closed by product [57], $E(G, t_i)$ is a visibly pushdown language. As a concatenation of visibly pushdown languages, $E(G, t)$ is visibly pushdown. The rest of the proof is similar. $\square$

These results could not be extended directly to LL($k$) grammars (not even LL(1) grammars) as they are not closed by concatenation [60].

The previous theorems are limited to deterministic grammars. It would be interesting to see whether the intent-equivalence could be decidable for more general context-free grammars. However, the following theorem shows that this is undecidable even for a single blank and for a subset of context-free grammars.

**Theorem 5.20.** Let $G$ be a linear grammar, $(p, s)$ a template and $t \in \Delta$. It is undecidable whether $(p, s)$ is intent-equivalent to $i$. $\square$

**Proof.** Let $G_1 = (N_1, T, R_1, S_1)$ and $G_2 = (N_2, T, R_2, S_2)$ two linear grammars. Let $S_3, S'_2, \#_1, \#_2$ be new symbols and $G_3 = (T_3 = T \cup \{\#_1, \#_2\}, N_3 = N_1 \cup N_2 \cup \{S'_2, S_3\}, R_3 = R_1 \cup R_2 \cup R', S_3)$ where $R'$ is defined as:

$$S_3 \to \#_1 S_1 \qquad S_3 \to \#_1 S'_2 \qquad S'_2 \to S_2 \qquad S'_2 \to \#_2$$

Due to the rules in $R'$, $F(L(G_3), (\#_1, \epsilon)) = L(G_1) \cup L(G_2) \cup \{\#_2\}$. Let search what symbol $t \in T_3 \cup N_3$ can explain these injections. We can break this search into four cases:

1. $t \neq S_3, t \neq S'_2, t \neq \#_2$. Then $E(G_3, t)$ does not contain the symbol $\#_2$ so $F(L_3, (\#_1, \epsilon)) \neq E(G_3, t)$.

2. $t = \#_2$. Then $E(G_3, t) = \{\#_2\}$ and $F(L(G_3), (\#_1, \epsilon)) \neq E(G_3, t)$ iff $L(G_1) = L(G_2) = \emptyset$.

3. $t = S_3$. But $S_3 \nrightarrow_{G_3}^* \#_1 S_3$, so $(\#_1, \epsilon)$ cannot be intent-equivalent to $S_3$.

4. $t = S'_2$. $S_3 \Rightarrow_{G_3}^* \#_1 S'_2$ so it is a suitable candidate and $E(G, S'_2) = L(G_2) \cup \{\#_2\}$.

Since $(\#_1, \epsilon)$ might only be intent-equivalent to $S'_2$ or $\#_2$, we deduce that:

($\#_1, \epsilon$) is intent-equivalent to some $t$

$$\Leftrightarrow F(L(G_3), (\#_1, \epsilon)) \neq E(G_3, t) \lor F(L(G_3), (\#_1, \epsilon)) \neq E(G_3, t)$$

$$\Leftrightarrow (L(G_1) \cup L(G_2) \cup \{\#_2\}) = (L(G_2) \cup \{\#_2\}) \lor L(G_1) = L(G_2) = \emptyset$$

$$\Leftrightarrow L(G_1) - L(G_2) = \emptyset$$

$$\Leftrightarrow L(G_1) \subseteq L(G_2)$$

The grammar $G_3$ is linear (due to the linearity of $G_1$ and $G_2$ and the form of the new rules), so if the intent-equivalence for linear grammars were decidable, then $L(G_1) \subseteq L(G_2)$ would be decidable. Because the latter is undecidable [63,64] we conclude that the intent-equivalence is undecidable for linear grammars. $\square$

**Corollary 5.21.** Let $G$ be a context-free grammar, $(p, s)$ a template and $t \in \Delta$. It is undecidable whether $(p, s)$ is intent-equivalent to $i$. $\square$

**Proof.** Context-free grammars are a superset of linear grammars. $\square$
The origin of this undecidability is that the set of expected injections can be very complex. If we impose the intents to be composed of terminals only, the set of expected injections will be finite. In that case, the intent-decidability is decidable for context-free languages.

**Theorem 5.22.** Let $G$ be a context-free grammar, $m \ge 1$, $t$ a template with $m$ blanks and $\iota \in (T^+)^m$, so $\iota$ can only contain terminals. It is decidable whether $t$ is intent-equivalent to $\iota$.

**Proof.** Once again, the proof is similar to the proof of **Theorem 5.14**. Context-free languages are closed by inverse homomorphism, so $L_1$ is context-free. They are also closed by intersection with a regular language, so $L_1 \cap L_2$ is context-free. Because each $E(G, \iota_i) = \{\iota_i\}$ (due to $\iota_i \in T^+$) and because $f_i(F(L, \iota))$ is a concatenation of context-free languages, $f_i(F(L, \iota))$ is context-free. So $F(L, \iota)$ is context-free and $E(G, \iota)$ is finite, therefore $F(L, \iota) - E(G, \iota)$ is context-free and its emptiness is decidable. We can conclude that it is decidable whether $t$ is intent-equivalent to $\iota$. $\square$

This last result is interesting because the intents of the developer are generally composed of one token, i.e., one terminal.

**Theorems 5.14, 5.16 and 5.17** indicate that security solutions through template analysis (e.g., by static analysis of the source code) can be useful as long as the developer's intent is known and the grammar is regular or LR(0). When the developer's intent length is 1, such analysis can also be performed on LR($k$) grammars. When it is composed of terminals only, it is even possible on any context-free grammar. In the general case, however, even when the template and the developer's intent are known, it is undecidable whether unexpected injections can happen in linear or context-free grammars due to **Theorem 5.21**. The question of the decidability of the intent-equivalence for any intent is still open for deterministic context-free grammars.

The definitions of this section allow us to show whether some template is safe or not. However, this definition cannot be used to prove that a whole grammar is safe when the language is infinite. This is the subject of the next section.

# 6. Intent-security

## 6.1. Formal definition of the intent-security

The goal of this subsection is to propose a property that guarantees that a grammar is safe. Consider the following case, where a developer has some intent in mind. For example, they expect the user to provide an attribute name in a SQL query. Can they be guaranteed that any template written for that intent is intent-equivalent to their intent?

Let us first define the set of injections for a given intent for all templates. This set contains all words that could replace an expected injection among all templates. In the following, every definition are given with respect to a grammar $G = (N, T, R, S)$.

**Definition 6.1.** Let $\iota \in \Delta^+$ be a sentential form. The language of injections of $G$ for intent $\iota$, written $I(G, \iota)$, is the language defined by:

$$I(G, \iota) = \{w \in T^* \mid \exists p, s \in T^* : pws \in L(G), S \Rightarrow^* pts\}$$

In all these injections, some may comply with the intent $\iota$ and be expected (and legitimate), and some may be unexpected.

**Definition 6.2** (Unexpected injections of $G$ for intent $\iota$). Let $\iota \in \Delta^+$. The language of *unexpected injections of $G$ for intent $\iota$*, noted $\delta I(G, \iota)$, is defined as:

$$\delta I(G, \iota) = \{w \in T^* \mid \exists p, s \in T^* : pws \in L(G), S \Rightarrow^* pts, \iota \not\Rightarrow^* w\}$$

**Remark 6.3.** By relying on expected injections, we propose an alternative definition of unexpected injections: Let $\iota \in \Delta^+$. The language of unexpected injections of $G$ for intent $\iota$ can be defined as:

$$\delta I(G, \iota) = I(G, \iota) - E(G, \iota)$$

The two definitions are equivalent:

$$\begin{align*}
\delta I(G, \iota) &= \{w \in T^* \mid \exists p, s \in T^* : pws \in L(G) \text{ and } S \Rightarrow^* pts \text{ and } \iota \not\Rightarrow^* w\} \\
&= \{w \in T^* \mid \exists p, s \in T^* : pws \in L(G) \text{ and } S \Rightarrow^* pts\} - \{w \in T^* \mid \iota \Rightarrow^* w\} \\
&= I(G, \iota) - E(G, \iota)
\end{align*}$$

We can use this set of unexpected injections of $G$ for intent $\iota$ to define properly the property of intent-security we describe earlier: an intent-secure grammar has no unexpected injections.

**Definition 6.4** (Intent-secure grammar for an intent). Let $\iota \in \Delta^+$. A formal grammar $G$ is said to be *intent-secure for $\iota$* if there are no unexpected injections for that intent, i.e.:

$$\delta I(G, \iota) = \emptyset$$

Since the intent-security holds for every prefix and suffix, it intuitively means that it is stronger than intent-equivalence. This is confirmed by the next proposition:

**Proposition 6.5.** Let $\iota \in \Delta^+$. $G$ is intent-secure for $\iota$ if and only if, for all templates $(p, s)$ such that $S \Rightarrow^* pts$, $(p, s)$ is intent-equivalent to $\iota$.
**Proof.**

$$
\begin{align*}
G \text{ is intent-secure for } t &\iff \delta I(G, t) = \emptyset \\
&\iff I(G, t) \subseteq E(G, t) \\
&\iff t \Rightarrow^* w \text{ for all } w, p, s \in T^* \text{ such that } pws \in L(G) \text{ and } S \Rightarrow^* pts \\
&\iff (p, s) \text{ is intent-equivalent to } t \text{ for all } (p, s) \in T^* \text{ such that } S \Rightarrow^* pts
\end{align*}
$$

□

This result highlights the potential of grammar analysis. If one can prove that a grammar is intent-secure for some intent, then it
means that a developer with that intent will always write templates that allow only legitimate injections.

Furthermore, we define the set of unexpected injections of *G* over all intents with length *n*:

**Definition 6.6** (Unexpected injections of *G* for all intent of length *n*). Let *n* ≥ 1. The set of *unexpected injections of G over all intents with length n*, noted *δI*<sup>*n*</sup>(*G*), is defined as:

$$
\delta I^n(G) = \{ \delta I(G, t) \mid t \in \Delta^n \}
$$

Remark that $\delta I^n(G)$ is a set of languages and not a language. For this reason, we use the calligraphic font $I$ and not $I$.

We could define the intent-security of a grammar as the property of being intent-secure for all possible intent. However, with that naive definition, nearly all grammars would be intent-insecure, as indicated by the following result.

**Proposition 6.7.** Let $G$ be a grammar such that $|L(G)| \ge 2$ and let $l$ be the minimal length of the words of $L(G)$. Then $G$ is not intent-secure over all intents with length $l$.

**Proof.** Let $w_1$ be a word of smallest length in $L(G)$ and $w_2 \in L(G)$ such that $w_1 \neq w_2$. Remark that $S \Rightarrow^* w_1, S \Rightarrow^* w_2$ and $w_1 \nrightarrow^* w_2$. So $w_2 \in \delta I(G, w_1)$. $\square$

So a grammar of practical interest cannot be intent-secure for any intent length. For this reason, we will define the intent-security of a grammar for some length of intent.

**Definition 6.8** (Intent-secure grammar for intent length *n*). Let *n* ≥ 1. A formal grammar *G* is said to be *intent-secure for intent length* *n* if, for every intent of length equal to *n*, all injections are expected, i.e.:

$$
\delta I^n(G) = \{\emptyset\}
$$

That means that a grammar can be intent-secure for simple intents whose length are 1, but not intent-secure for more complex
intents. Let us illustrate this property with an infinite language that is intent-secure for intent length 1.

**Proposition 6.9.** There exist context-free grammars generating infinite languages that are intent-secure for intent length 1.

**Proof.** Let us consider the grammar $G = (\{a, b, c, d\}, \{S\}, R, S)$ where $R = \{S \to aSb; S \to cd\}$. A simple proof by induction shows that $L(G) = \{a^n cdb^n \mid n \ge 0\}$. Each word in $L(G)$ contains exactly one occurrence of the symbols $c$ and $d$ and contains as many $a$ symbols as $b$ symbols. All $a$ symbols (resp. $b$ symbols) of a word in $L(G)$ are before the symbol $c$ (resp. after the symbol $d$).

The grammar *G* contains one non-terminal *S* and four terminals {*a*, *b*, *c*, *d*}. So there are only five different intents of length 1:

* Case 1: $t = a$. Due to the form of the words in $L(G)$, a query with a injection in $a$ has the form $a^m a^t c^r c^d b^n$, with $m, n, r \ge 0$. Since the word $a^m a^r c^d b^n$ belongs to $L(G)$, $m + 1 + r = n$, so $r = n - 1 - m$ and $a^{m-1} a^{n-1} c^r c^d b^n$. The query already contains the symbols $c$ and $d$. Therefore, a valid injection cannot contain these symbols. The symbol $t$ is to the left of the $c$ symbol. Therefore, a valid injection cannot contain a $b$ symbol and a valid injection contains only $a$ symbols. In order to balance the number of $a$ symbols and $b$ symbols, the injection must contain only one $a$ symbol. Finally, the only valid injection is $a$ and $\delta I(G, a) = \{a\} - \{a\} = \emptyset$.

* Case 2: $t = c$. A valid injection must include exactly one $c$ and no $d$ because there must be exactly one $c$ and one $d$ in the query. There cannot be any $b$ in this injection because all $b$ are after $d$. If this injection contains one or more $a$, there will be strictly more $a$ than $b$ in the query. So, finally, the only valid injection is $c$.

* Case 3: $t = d$. Similar to case 2.

* Case 4: $t = b$. Similar to case 1.

* Case 5: $t = S$. A simple induction shows that all sentential forms with this injection point have the following form: $a^n c^d b^m$, with $n \ge 0$. The set of injections is therefore $I(G, S) = \bigcup_{n \ge 0} a^n \setminus L/b^m = \{a^m c^d b^m \mid m \ge 0\} = E(G, S)$. So $\delta I(G, S) = \emptyset$.

Finally, $\delta I(G) = \{\emptyset\}$. $\square$

We succinctly extend the previous definitions to injections in multiple-blanks templates.

**Definition 6.10** (Injections of *G* for intents *t*). Let *m* ≥ 1 and *t* ∈ (Δ⁺)ⁿ. We define the language of *injections of G at t* as the language defined by:

$$
I(G, t) = \{ w \in (T^*)^m \mid \exists t \in T^* \times (T^+)^{m-1} \times T^* : t \odot w \in L(G) \text{ and } S \Rightarrow^* t \odot t \}
$$
**Definition 6.11** (Unexpected injections of G for intents $t$). Let $m \ge 1$ and $t \in (\Delta^+)^m$. We define the language of unexpected injections of G at $t$ as the language defined by:

$$ \delta I(G, t) = I(G, t) - E(G, t) $$

Because intents may have different lengths for templates with multiple blanks, we define the intent-security with a constraint on the maximum length of each element of the intent.

**Definition 6.12** (Intent-secure grammar with multiple blanks). A formal grammar G is said to be intent secure with m blanks for intent length at most n if, for all intent $t \in (\bigcup_{k=1}^n \Delta^k)^m$, $\delta I(G, t) = \emptyset$.

As we will see later, a grammar can be intent-secure for one blank but not intent-secure for multiple blanks.

## 6.2. Inherently intent-secure and inherently intent-insecure languages

In the previous subsection, we defined the notion of intent-security for grammars only, for the reasons detailed in Section 4. However, the intuition tells us that some languages are not intent-secure, no matter what grammar is used. So, in this subsection, we define the notion of inherently intent-secure and inherently intent-insecure languages.

**Definition 6.13** (Inherently intent-secure language for intent length $n$). Let $L$ be a formal language. $L$ is inherently intent-secure on intent length $n$ if all context-free grammars $G$ such that $L(G) = L$ are intent-secure on intent length $n$.

Even though the notion of inherently intent-secure languages may appear attractive, the following theorem shows that it is not a property that useful languages can verify.

**Proposition 6.14.** Inherently intent-secure languages for intent length 1 contain at most one word.

**Proof.** Let $G = (N, T, R, S)$ be a grammar that describes a language $L$ with at least two words, $w_1$ and $w_2$. Let us show that we can create $G'$ such that $G'$ is not intent-secure and $L(G') = L$. Denote $\alpha_1, \alpha_2, \dots$ and $\alpha'_1, \alpha'_2, \dots$ such that $S \Rightarrow_L \alpha_1 \Rightarrow_L \alpha_2 \Rightarrow_L \dots \Rightarrow_L w_1$ is a left derivation of $w_1$ and $S \Rightarrow_L \alpha'_1 \Rightarrow_L \alpha'_2 \Rightarrow_L \dots \Rightarrow_L w_2$ is a left derivation of $w_2$. Let $k$ be such that $\alpha_k = \alpha'_k$ and $\alpha_{k+1} \neq \alpha'_{k+1}$ ($k$ exists since the starts of the derivations are the same and the ends are different). Denote $A$ the leftmost nonterminal of $\alpha_k$ that is derived and denote $A \to \beta$ the production rule used in the left derivation of $w_1$ and $A \to \gamma$ the production rule used in the left derivation of $w_2$. Let us compare the languages $L_\beta = \{w \mid \beta \Rightarrow^* w\}$ and $L_\gamma = \{w \mid \gamma \Rightarrow^* w\}$. If $L_\beta = L_\gamma$, we can remove the rule $A \to \gamma$ from $R$ and it would still describe the same language. We could therefore use the same reasoning with this new grammar to identify $\beta'$ and $\gamma'$. Since the number of production rules is finite, at some point we will identify some $\beta''$ and $\gamma''$ such that $L_{\beta''} \neq L_{\gamma''}$. So, let's assume that $L_\beta \neq L_\gamma$ and denote (without loss of generality) $w$ such that $w \in L_\beta$ and $w \notin L_\gamma$, i.e., $\beta \Rightarrow^* w$ and $\gamma \Rightarrow^* w$.

Let us construct $G' = (N \cup \{B\}, T, R', S)$ where $B$ is a new nonterminal and $R'$ is defined as $(R \setminus \{A \to \gamma\}) \cup \{A \to B, B \to \gamma\}$. Remark that $L(G') = L(G)$. Let $pAs$ a sentential form that can be derived from $S$ in $G$. So $S \Rightarrow_{G'}^* pBs$. Furthermore, $S \Rightarrow_{G'}^* pAs \Rightarrow p\beta s \Rightarrow_{G'}^* pws$. However, since $\gamma \Rightarrow^* w$, we can conclude that $B \Rightarrow^* w$ and therefore that $w \in \delta I(G', B)$. So $L$ is not inherently intent-secure. $\square$

We similarly define inherently intent-insecure languages.

**Definition 6.15** (Inherently intent-insecure language for intent length $n$). Let $L$ be a formal language. $L$ is inherently intent-insecure for intent length $n$ if all context-free grammars $G$ such that $L(G) = L$ are intent-insecure for intent length $n$.

In a similar fashion, a language is intent-insecure for $m$ blanks if all its context-free grammars are intent-insecure for $m$ blanks. The next proposition shows a sufficient condition for a language to be inherently insecure.

**Proposition 6.16.** Let $L$ be a language, $n \ge 1$. If there exist $p, s \in T^*$, $z \in T^n$ and $w \in T^*$ such that $z \neq w$, $pzs \in L$ and $pws \in L$, then $L$ is inherently intent-insecure for $n$.

**Proof.** Let $G$ such that $L(G) = L$. Then $w \in \delta I(G, z)$ so $\delta I(G, z) \neq \emptyset$. Since this is true for any grammar $G$, we can conclude that $L$ is inherently intent-insecure. $\square$

It is still an open question of whether an inherently intent-insecure language for intent length 1 can be intent-secure for all intents consisting of a unique terminal.

This result can be applied to easily show that a language is inherently intent-insecure with a single counterexample. This is applied to popular programming languages in the next subsection.

## 6.3. Monotonicity properties

Let us exhibit some properties about the monotonic behavior of unexpected injections. Indeed, usual advice for developers is to use the least powerful language suitable for one task [44] with the intuition that simpler languages are less prone to injection vulnerabilities. In this subsection, we explore such kinds of properties and whether they hold in our framework.

Without any surprises, we can prove a monotonic property of unexpected injections for unambiguous grammars and, therefore, for deterministic grammars.
**Theorem 6.17.** Let two unambiguous grammars $G_1 = (N, T, R_1, S)$ and $G_2 = (N, T, R_2, S)$ such that $R_1 \subseteq R_2$. Then $\delta I(G_1, t) \subseteq \delta I(G_2, t)$ for all $t \in \Delta^+$.

**Proof.** Let $t \in \Delta^+$, $w \in T^*$ such that $w \in \delta I(G_1, t)$. Let us show that $w \in \delta I(G_2, t)$. Given that $w \in \delta I(G_1, t)$, we know that there exist $p, s \in T^*$ such that $pws \in L(G_1)$, $S \Rightarrow^*_{G_1} pis$ and $t \not\Rightarrow^*_{G_1} w$. Since $R_1 \subseteq R_2$, $\alpha \Rightarrow^*_{G_1} \beta$ implies that $\alpha \Rightarrow^*_{G_2} \beta$ because all the rules used to derive $\beta$ from $\alpha$ in $G_1$ can be used in $G_2$. Therefore, $pws \in L(G_2)$, $S \Rightarrow^*_{G_2} pis$.

Let us prove that $t \not\Rightarrow^*_{G_2} w$ by contradiction, by assuming that $t \Rightarrow^*_{G_2} w$ and showing that $G_2$ cannot be unambiguous. Since $t \not\Rightarrow^*_{G_1} w$, it means that at least one rule in $R_2$ but not in $R_1$ is used to derive $w$ from $t$ in $G_2$. So, there is a derivation path from $S$ to $pws$ that uses at least one rule from $R_2 - R_1$. On the other hand, since $S \Rightarrow^*_{G_1} pws$, that there is another derivation path from $S$ to $pws$ that only use rules from $R_1$. We created two different derivation paths from $S$ to $pws$ in $G_2$, which is in contradiction with it being unambiguous. Therefore, we can conclude that the assumption $t \Rightarrow^*_{G_2} w$ is false.

Since we proved that $pws \in L(G_2)$, $S \Rightarrow^*_{G_2} pis$ and $t \not\Rightarrow^*_{G_2} w$, we conclude that $w \in \delta I(G_2, t)$ and finally that $\delta I(G_1, t) \subseteq \delta I(G_2, t)$ for any $t \in \Delta^+$. $\square$

This result motivates the advice mentioned above as it applies to the widely used unambiguous grammars. However, such monotonic property is not true in the general case, as shown with the following counterexample.

**Remark 6.18.** There exist two context-free grammars $G_1 = (N, T, R_1, S)$ and $G_2 = (N, T, R_2, S)$ such that $R_1 \subseteq R_2$ and $\delta I(G_1, t) \not\subseteq \delta I(G_2, t)$ for some $t \in N$.

Let $T = \{a, b, c\}$, $N = \{S, M\}$, $R_1 = \{S \to aaM, S \to aabb, M \to cc\}$ and $R_2 = \{S \to aaM, S \to aabb, M \to cc, M \to bb\}$. Thus, $R_1 \subseteq R_2$ and $L(G_1) = L(G_2) = \{aabb, aacc\}$. $E(G_2, M) = \{bb, cc\}$.

The terminals go in pairs. For a blank corresponding to a terminal intent, the only possible value is entirely determined by one of the surrounding terminals. Thus, for any terminal $t \in T$, $\delta I(G_1, t) = \emptyset$ and $\delta I(G_2, t) = \emptyset$. For the axiom, we necessarily have $\delta I(G_1, S) = \delta I(G_2, S) = \emptyset$. The only sentential form containing $M$ is $aaM$, for both grammars. Thus, $I(G_1, M) = \{bb, cc\}$. Since $E(G_1, M) = \{cc\}$, we conclude that $\delta I(G_1, M) = \{bb\}$. On the other hand, $E(G_2, M) = \{bb, cc\}$ so $\delta I(G_2, M) = \emptyset$.

We can also derive a monotonic property on languages (and not grammars), provided we restrict the analysis to terminal intents.

**Proposition 6.19.** Let $G_1$ and $G_2$ be two grammars such that $L(G_1) \subseteq L(G_2)$. Let $n \ge 1$, $t \in T^n$. Then $\delta I(G_1, t) \subseteq \delta I(G_2, t)$.

**Proof.**

$$ 
\begin{align*}
w \in \delta I(G_1, t) &\Rightarrow pws \in L(G_1), pis \in L(G_1), w \neq t \\
&\Rightarrow pws \in L(G_2), pis \in L(G_2), w \neq t \\
&\Rightarrow w \in \delta I(G_2, t)
\end{align*}
$$

$$ \text{So } \delta I(G_1, t) \subseteq \delta I(G_2, t). \quad \square $$

Finally, even though one may assume that intent-security for some intent length implies intent-security for lower intent length, it is not the case, as shown by the following counterexample.

**Remark 6.20.** Let $n, p$ such that $p > n \ge 1$. There exists a grammar $G$ that is intent-secure for intent length $p$ but not intent-secure for intent length $n$.

The grammar $G = (\{a, b, c, d\}, \{S, S'\}, \{S \to S'; S \to d^n; S' \to aS'b; S' \to c^{p+1}\}, S)$ describes the language $\{d^n\} \cup \{a^k c^{p+1} b^k \mid k \ge 0\}$. This grammar is intent-secure for intent length $p$ (the proof is similar to the one of Proposition 6.9) but is not intent-secure for intent length $n$ as the intent $d^n$ in the empty template $(\epsilon, \epsilon)$ can be replaced by the unexpected injection $c^{p+1}$.

## 6.4. Applications to some programming languages

As expected, many of the languages commonly used are inherently intent-insecure for intent length 1. To show this, we use the Proposition 6.16 and expose templates that allow unexpected injections when the intent is a single symbol (more precisely, a token).

### 6.4.1. SQL

The SQL language and its multiple dialects are infamous for their injection vulnerabilities. Here is a classic example:

SELECT * FROM product WHERE price = —

Let us assume that the intent is a number or a string. However, unexpected injections are possible, such as 123 OR availability='true' . This shows that the SQL language is inherently intent-insecure.

### 6.4.2. SMTP

SMTP (Simple mail transfer protocol) is a protocol used for email transmission. It is known to be prone to injection attack in its header. Consider the following template:

Here, the intent is a string containing an email address. However, unexpected injections are possible, such as sender=test.com%0Acc:victim@example.com that sends a carbon copy to someone else (the character %0A is used to add a new line). So the SMTP language is inherently intent-insecure.
1 To: recipient@example.com

2 From: __

3 Subject: an email

4 some text

5 .

6.4.3. LDAP

LDAP (Lightweight directory access protocol) is a protocol used for directory services. It is notably used for authentication. It
contain vulnerable templates, such as:

(& (USER=___)(PASSWORD=password))

Suppose the intent is a username. Unexpected injections are possible in this template, such as username) (&). So the LDAP language
is inherently intent-insecure.

6.4.4. Markup languages

Markup languages are a family of languages that share a structure composed of nested tags. For example, XML documents are
generally vulnerable to injection attacks, where an attacker closes and opens tags.

1 <?xml version="1.0" encoding="ISO-8859-1"?>

2 <users> <user> <login>user1</login>

3 <pwd>password1</pwd>

4 <root>false <root/>

5 <mail>user1@example.com</mail>

6 </user>

7 <user> <login>user2</login>

8 <pwd>password2</pwd>

9 <root>false <root/>

10 <mail> __ </mail>

11 </user>

12 </users>

The intent is an email address. However, unexpected injections are possible, such as:

1 not_suspicious@example.com</user>

2 <user> <login>root attacker</login>

3 <pwd>toor</pwd>

4 <root>true</root>

5 <mail>attacker@example.com</mail>

so the XML languages can be inherently intent-insecure. Such injections are also possible with other markup languages, such as
HTML, SVG or TeX.

6.4.5. Intent-secure markup languages

The previous subsection shows an inherently intent-insecure XML language. But they are infinitely many XML languages (it is a
whole language class [65]), and not all of them are inherently intent-insecure.

A simple way of constructing such an intent-secure XML language for an intent length 1 is based on the Proposition 6.9. Suppose
the objective is to represent a list of pairs (key, value). A first naive, intent-insecure language relies on the following document type
definition (DTD):

1<!ELEMENT l ((k, v)*)>

2<!ELEMENT k (#PCDATA)>

3<!ELEMENT v (#PCDATA)>

This DTD can be expressed as the grammar $G = (\langle \mathbf{l} \rangle, \langle \mathbf{l} \rangle, \langle \mathbf{k} \rangle, \langle \mathbf{k} \rangle, \langle \mathbf{v} \rangle, \langle \mathbf{v} \rangle, \mathbf{s}, \{S, A\}, R, S) $ where $R = \{S \to \langle \mathbf{l} \rangle A \langle \mathbf{l} \rangle, A \to \langle \mathbf{k} \rangle S \langle \mathbf{k} \rangle \langle \mathbf{v} \rangle S \langle \mathbf{v} \rangle A, A \to \mathbf{e} \}$ and $\mathbf{s}$ is any text.
Considering this example: `<1><k>first key</k>__</1>` Let us assume the intent is a tag v. However, unexpected inferences are possible, such that `<v>first value</v><k>second key</k><v>second value</v>`. So this DTD represents a vulnerable XML language.

However, instead of chaining the pairs, we can make them nested. We get the following DTD:

1 `<!ELEMENT l ((k, 1, v) | (c, d))>`

2 `<!ELEMENT k (#PCDATA)>`

3 `<!ELEMENT v (#PCDATA)>`

4 `<!ELEMENT c EMPTY>`

5 `<!ELEMENT d EMPTY>`

This DTD can be expressed as the grammar $G = (T, \{S, A\}, R, S)$ where

* $T = \{<1>, <1>, <k>, <k>, <1>, <v>, <v>, <c>, <d>, <s}\}$

* $R = \{S \to <1><k>s</k>S<v>s</v><1>, S \to <1><c></c><d></d><1}\}$

* s is any text.

The previous example must be changed to comply with this second DTD.

1 `<1><k>first key</k>`

2 `<1><k>second key</k><1><c></c><d></d><1>__</1>`

3 `<v>first value</v>`

4 `</1>`

In this example, the only possibility is to add the tag v: no unexpected injection is possible. The demonstration of the intent-security for intent length 1 of this grammar is similar to the proof of Proposition 6.9.

## 6.5. Decidability of intent-security

This subsection is dedicated to analyzing the decidability of the intent-security for classic classes of grammars: finite, regular, deterministic, and context-free. The intent-security of a grammar could greatly help the risk analysis of using that grammar and provide guarantees about its usage in critical systems.

**Proposition 6.21.** The intent-security with *m* blanks for intent length at most *n* of a context-free grammar that generates a finite language is decidable with the Algorithm 1.

**Algorithm 1:** Intent-security verification for finite languages.

**Input:** A context-free grammar $G = (N, T, R, S)$ that generates a finite language

**Input:** $n \ge 1$, the maximum intent length, $m \ge 1$, the number of blanks

**Output:** True if $G$ is intent-secure with $m$ blanks for intent length at most $n$, False otherwise

1. Remove from $G$ all the symbols that are unreachable from $S$;

2. **forall** $t \in (\bigcup_{k=1}^n \Delta^k)^m$ **do**

3. $T_t \leftarrow \{t \in T^* \times (T^+)^{m-1} \times T^* \mid S \Rightarrow^* t \odot t\}$; // Compute all possible templates

4. $I_t \leftarrow \{w \in (T^*)^m \mid \exists t \in T_t : S \Rightarrow^* t \odot w\}$; // Compute all possible injections

5. $U_t \leftarrow \{w \in I_t \mid \exists i \in [1, m] : t_i \Rightarrow^* w_i\}$; // Keep the injections that are not explainable by the intent

6. **if** $U_t \neq \emptyset$ **then** **return** False;

7. **return** True

*Proof sketch.* The termination of this algorithm is trivial since every operation involves finite sets. The variable $U_t$ is the set of injections of $I_t$ that cannot be derived from $t$, i.e., $U_t = \delta I(G, t)$. It is empty for all $t$ if and only if the grammar is intent-secure.

Finite languages can be used in simple message protocols for embedded systems. In that case, this naive algorithm can be very useful to prove that a grammar of such language is intent-secure. However, such a result cannot be obtained for infinite regular languages. In fact, these languages are inherently insecure due to the pumping lemma.

**Theorem 6.22.** Let $n \ge 1$. Infinite regular languages are inherently insecure for intent length $n$.
**Proof.** Let $L$ be an infinite regular language. By the pumping lemma for regular languages, there exists an integer $l > 0$ depending only on $L$ such that every word $w \in L$ of length at least $l$ can be written as $w = xyz$, satisfying the following conditions:

1. $|y| \ge 1$

2. $|xy| \le l$

3. $\forall k \ge 0$, $xy^k z \in L(G)$

As $|y| \ge 1$, $|y^n| \ge n$. Let $w, w'$ such that $|w| = n$ and $ww' = y^n$. Remark that there exist $w''$ such that $|w''| \ge 1$ and $ww''w' = y^{n+1}$. Let $p = x, s = w'z$. Then $pws = py^n z \in L$, $pww''s = py^{n+1} z \in L$ and $w \ne ww''$ so we can conclude with **Proposition 6.16** that $L$ is inherently intent-insecure for intent length $n$. ☐

This theorem may appear of little interest, as regular languages are rarely used in programming languages. However, due to the **Proposition 6.19**, we can conclude that any language that includes an infinite regular language is also inherently intent-insecure.

**Corollary 6.23.** Let $L$ be a formal language and $L_r$ be an infinite grammar language such that $L_r \subseteq L$. Then $L$ is inherently intent-insecure.

**Proof.** Direct application of **Proposition 6.19** and **Theorem 6.22**. ☐

In particular, if any nonterminal derives an infinite regular language in a formal grammar, then its language is inherently intent-insecure. Since such constructions are ubiquitous in programming languages (for example, any list of elements separated by commas), it explains their vulnerability to injection-based attacks.

**Example 6.24.** The classic SQL injection 'OR '1'='1 can be viewed as an injection in the infinite regular sublanguage SELECT * FROM table WHERE (<Condition> OR)* <Condition> where the symbols <Condition> OR are pumped by the injection. This is also the case for piggy-backed SQL injections that rely on the (<Query> );)* <Query> regular sublanguage and for UNION-based SQL injections that rely on the (<Select Query> UNION)* <Select Query> regular sublanguage.

In fact, this is also the case for OS command injection (<Command> );)* <Command>, for SMTP “To” and “From” injection (<Email> %0A cc:)* <Email>, for LDAP injection (cf. **Example 5.3**), and many more.

While regular infinite languages are inherently insecure, their set of unexpected injections are regular and can be easily computed. However, in most cases, the set of unexpected injections lies in a language class that is more complex than that of the query language. As an example, the following proposition shows a simple LL(1) grammar with context-sensitive unexpected injections.

**Proposition 6.25.** Consider two context-free grammars $G_1 = (\{S_1, N_1\}, T, R_1, S_1)$, $G_2 = (\{S_2, N_2\}, T, R_2, S_2)$ with $T = \{k, d, a, \hat{a}, \hat{v}\}$ and the following rules:

Let $G = (\{S, S_1, N_1, S_2, N_2\}, T, R \cup R_1 \cup R_2, S)$. The grammar $G$ is a LL(1) grammar and its injection language $\delta I(G, k)$ is context-sensitive and not context-free.

<table><thead><tr><th>R</th><th>R<sub>1</sub></th><th>R<sub>2</sub></th></tr></thead><tbody><tr><td>S &rarr; a N<sub>2</sub></td><td>S<sub>1</sub> &rarr; k v N<sub>1</sub> v</td><td>S<sub>2</sub> &rarr; a N<sub>2</sub></td></tr><tr><td>S &rarr; v&#770; S<sub>2</sub> v</td><td>N<sub>1</sub> &rarr; v N<sub>1</sub> v</td><td>S<sub>2</sub> &rarr; v&#770; S<sub>2</sub> v</td></tr><tr><td>S &rarr; v&#770; S<sub>2</sub> v&#770;</td><td>N<sub>1</sub> &rarr; v&#770; N<sub>1</sub> v&#770;</td><td>S<sub>2</sub> &rarr; v&#770; S<sub>2</sub> v&#770;</td></tr><tr><td>S &rarr; â&#770; S<sub>2</sub> a</td><td>N<sub>1</sub> &rarr; a N<sub>1</sub> a</td><td>S<sub>2</sub> &rarr; â&#770; S<sub>2</sub> a</td></tr><tr><td>S &rarr; S<sub>1</sub></td><td>N<sub>1</sub> &rarr; â&#770; N<sub>1</sub> â&#770;</td><td>N<sub>2</sub> &rarr; a S<sub>2</sub> â&#770;</td></tr><tr><td></td><td>N<sub>1</sub> &rarr; d</td><td>N<sub>2</sub> &rarr; v d</td></tr></tbody></table>

**Proof.** We first prove that $G$ is indeed an LL(1) grammar by exhibiting its LL(1) parsing table in **Table 5**.

Let $L_1 = L(G_1)$ and $L_2 = L(G_2)$. The language $L_1$ is simply $\{kv\alpha'r'dav | \alpha \in \{a, \hat{a}, v, \hat{v}\}\}^*$. Our goal is to compute $I(G, k)$:

$$ 
\begin{aligned}
I(G, k) &= \{z \in T^* | \exists p, s \in T^*, pzs \in L, S \Rightarrow^* pks\} \\
&= \{z \in T^* | \exists \alpha \in \{a, \hat{a}, v, \hat{v}\}^*, zv\alpha'r'dav \in L\}
\end{aligned}
$$

This is justified by the fact that the words in $L$ that contain $k$ all come from $L_1$ (the words of $L_2$ cannot contain $k$), so necessarily $p = \epsilon$ and $s = v\alpha'r'dav$.

<table><caption>**Table 5**

LL(1) parsing table for the grammar $G$ defined in **Proposition 6.25**.</caption><thead><tr><th>$\$</th><th>a</th><th>v&#770;</th><th>v</th><th>â&#770;</th><th>k</th><th>d</th></tr></thead><tbody><tr><td>S</td><td>S &rarr; a N<sub>2</sub></td><td>S &rarr; v&#770; S<sub>2</sub> v</td><td>S &rarr; v&#770; S<sub>2</sub> v&#770;</td><td>S &rarr; â&#770; S<sub>2</sub> a</td><td>S &rarr; S<sub>1</sub><br>S<sub>1</sub> &rarr; k v N<sub>1</sub> v</td><td></td></tr><tr><td>S<sub>1</sub></td><td></td><td>N<sub>1</sub> &rarr; a N<sub>1</sub> a</td><td>N<sub>1</sub> &rarr; v&#770; N<sub>1</sub> v&#770;</td><td>N<sub>1</sub> &rarr; v N<sub>1</sub> v</td><td>N<sub>1</sub> &rarr; â&#770; N<sub>1</sub> â&#770;</td><td>N<sub>1</sub> &rarr; d</td></tr><tr><td>S<sub>2</sub></td><td>S<sub>2</sub> &rarr; a N<sub>2</sub></td><td>S<sub>2</sub> &rarr; v&#770; S<sub>2</sub> v</td><td>S<sub>2</sub> &rarr; v&#770; S<sub>2</sub> v&#770;</td><td>S<sub>2</sub> &rarr; â&#770; S<sub>2</sub> a</td><td></td><td></td></tr><tr><td>N<sub>2</sub></td><td>N<sub>2</sub> &rarr; a S<sub>2</sub> â&#770;</td><td></td><td>N<sub>2</sub> &rarr; v d</td><td></td><td></td><td></td></tr></tbody></table>
There is only one z such that $zva^rdav \in L_1$: k. This means that the words z such that $zva^rdav \in L_2$ are exactly the unexpected injections (since $E(G, k) = \{k\}$).

$$ \delta I(G, k) = \{z \in T^* | \exists \alpha \in \{a, \hat{a}, v, \hat{v}\}^*, zva^rdav \in L_2\} $$

In the following, the suffix palindrome ($vsa^rdav$) will be highlighted in blue. We want to prove that $\delta I(G, k) = \{\hat{v}a^{2^n} | n \ge 0\}$. To achieve this goal, we will first prove by induction on n that all words $\omega_1\omega_2$ from $L_2$ such that $\omega_1vsa^rdav \in L_2$ must have the form: $\omega_1\omega_2 = \hat{v}a^{2^n}(\prod_{0 \le i < n} \phi_i)^r d(\prod_{0 \le i < n} \phi_i)v$ for $n \ge 0$, where $\phi_i = va^{2^i}\hat{v}\hat{a}^{2^i}$.

In the following, $\gamma_i$ will be the sequence of words of $G_2$ obtained by a backward (bottom-up) derivation with the rules of $G_2$. The previous definition of $\delta I(G, k)$ shows that our goal is to obtain a word with a suffix that is a palindrome ending with $v$. We start from the smallest word of $L(G_2)$, $\gamma_0 = avd$. To get a palindrome around $d$, we need to add $v$ at the end of $avd$, and therefore use the rule $S_2 \to \hat{v}S_2v$ to obtain $\gamma_1 = \hat{v}avdv$. The sequence $\gamma_1$ ends with a palindrome $vdv$ that ends with $v$, hence the injection is $\hat{v}a$ as expected.

For $n=1$, we continue to make longer words from $\gamma_1 = \hat{v}avdv$. The prefix before the palindrome $vdv$ is $\hat{v}a$ so, to extend the palindrome, we need to add $a\hat{v}$ at the end of $\gamma_1$. It means that the sole possibility to continue is by using $S_2 \to \hat{a}S_2a$ and then $S_2 \to vS_2\hat{v}$, leading to $\gamma_2 = \hat{v}\hat{a}\hat{v}dv\hat{a}\hat{v}$. Because the added suffix $a\hat{v}$ does not end with $v$, we continue, guided by the added prefix $v\hat{a}$. We obtain $\gamma_3 = \hat{v}aav\hat{v}\hat{a}\hat{v}dv\hat{a}\hat{v}$ that ends with a $v$. This leads to the injection $\hat{v}aa$ as expected.

The same reasoning applies to the general case: let $\gamma_l = \hat{v}a^{2^n}v(\prod_{0 \le i < n} \phi_i)^r d(\prod_{0 \le i < n} \phi_i)v$. We are guided first by the prefix $\hat{v}a^{2^n}$, yielding: $\gamma_{l+1} = v\hat{a}^{2^n}\gamma_l a^{2^n}\hat{v}$. Since $\gamma_{l+1}$ does not end with $v$, we are then guided by the starting sequence $v\hat{a}^{2^n}$. We get: $\gamma_{l+2} = \hat{v}(aa)^{2^n}\gamma_{l+1}\hat{a}^{2^n}v$. Written completely, it is:

$$ \gamma_{l+2} = \hat{v}(aa)^{2^n} v \hat{a}^{2^n} \hat{a}^{2^n} v \left( \prod_{0 \le i < n} \phi_i \right)^r d \left( \prod_{0 \le i < n} \phi_i \right) v \hat{a}^{2^n} \hat{a}^{2^n} v $$

As $\phi_n = va^{2^n}\hat{v}\hat{a}^{2^n}$, $\gamma_{l+2}$ can finally be rewritten into:

$$ \gamma_{l+2} = \hat{v}a^{2^{n+1}} v \left( \prod_{0 \le i < n+1} \phi_i \right)^r d \left( \prod_{0 \le i < n+1} \phi_i \right) v $$

This completes the induction. In the end, $\delta I(G, k) = \{\hat{v}a^{2^l} | i \ge 0\}$: this language is well known to be context-sensitive but not context-free [52]. □

So the languages of unexpected injection can be much more complex than the initial grammar: in this case, an LL(1) grammar can yield a context-sensitive set of unexpected injections. Since the emptiness is undecidable for context-sensitive languages, this example suggests that the intent-security of a grammar (verified by the emptiness of its unexpected injection set) could be undecidable even for simple grammars. In fact, the next theorems show that the unexpected injection languages of LR(0) grammars can be any recursively enumerable languages, and so that their intent-security is not decidable.

Our theorems are based on the following lemma.

**Lemma 6.26.** For every recursively enumerable language $L$, there exist a regular set $R$ and two morphisms $g$ and $h$, such that

$$ L = \{g(w)/h(w) \mid w \in R\} $$

**Proof.** This proof is based on the proof of a similar theorem in [66]. We assume that $L$ is defined by a grammar $G = (N, T, R, S)$ and that each rule in $R$ is identified by a unique symbol: $R = \{r_i : \alpha_i \to \beta_i\}_{i \in I}$, where $I$ is a finite index set. In addition to symbols from $T$ and $N$, the authors introduce $|I| + 3$ new symbols, namely $A, B, \bar{B}$, and the symbols $\{r_i\}_{i \in I}$. The regular set $R_G^1 = A(B\Delta^*R\Delta^*)^*\bar{B}$ is defined, as well as the homomorphisms described in Table 6.

We focus on the intuition behind $R_G^1$. Consider the following derivation:

$$ \begin{align*} S &= \alpha_a \Rightarrow^{r_a} \beta_a = u_1 \alpha_b v_1 \\ &\Rightarrow^{r_b} u_1 \beta_b v_1 = u_2 \alpha_c v_2 \\ &\Rightarrow^{r_c} u_2 \beta_c v_2 \end{align*} $$

where $\Rightarrow^r$ indicates that the rule $r$ has been applied, and $u_i, v_i$ indicate in which context the rule has been applied. Let consider the word $w = ABr_a Bu_1r_b v_1 Bu_2r_c v_2 \bar{B}$ that belongs to $R_L^1$ and its image though $g_G$ and $h_G$:

<caption>**Table 6**</caption>

Morphisms $g_G$ and $h_G$ with $a \in \Delta$ and $r_i : \alpha_i \to \beta_i \in R$.

<table><thead><tr><th></th><th>A</th><th>B</th><th>B&#773;</th><th>a</th><th>r<sub>i</sub></th></tr></thead><tbody><tr><th>g<sub>G</sub></th><td>ABS</td><td>B</td><td>&epsilon;</td><td>a</td><td>&beta;<sub>i</sub></td></tr><tr><th>h<sub>G</sub></th><td>A</td><td>B</td><td>B</td><td>a</td><td>&alpha;<sub>i</sub></td></tr></tbody></table>
<caption>**Table 7**</caption>

Morphisms $g_{G'}^r$ and $h_{G'}^r$ with $a \in \Delta$ and $r_i : \alpha_i \to \beta_i \in R'$.

<table><thead><tr><th></th><th>A</th><th>B</th><th>B&#773;</th><th>a</th><th>r<sub>i</sub></th></tr></thead><tbody><tr><td>g<sub>G'</sub><sup>r</sup></td><td>SBA</td><td>B</td><td>&epsilon;</td><td>a</td><td>&beta;<sub>i</sub><sup>r</sup></td></tr><tr><td>h<sub>G'</sub><sup>r</sup></td><td>A</td><td>B</td><td>B</td><td>a</td><td>&alpha;<sub>i</sub><sup>r</sup></td></tr></tbody></table>

$$w = A \quad Br_a \quad Bu_1r_bv_1 \quad Bu_2r_cv_2 \quad \overline{B}$$

$$g_G(w) = ABS \quad B\beta_a \quad Bu_1\beta_bv_1 \quad Bu_2\beta_cv_2$$

$$h_G(w) = A \quad B\alpha_a \quad Bu_1\alpha_bv_1 \quad Bu_2\alpha_cv_2 \quad B$$

Remark that $h_G(w)$ is a prefix of $g_G(w)$: in this example, $S = \alpha_a$, $\beta_a = u_1\alpha_bv_1$ and $u_1\beta_bv_1 = u_2\alpha_cv_2$. In the end, $h_G(w) \setminus g_G(w)$ is the last sentential form of the derivation, in this case $u_2\beta_cv_2$. The quotient ensure that the derivation is valid. The theorem of [66] states that this quotient, when intersected with $T^*$, recreates exactly the words of the initial language and only those, i.e.,

$$L = \{h_G(w) \setminus g_G(w) \mid w \in \mathcal{R}_G^1\} \cap T^*$$

However, we can slightly modify this proof to omit this intersection with $T^*$. In fact, this intersection is used to rule out the intermediate forms that are not words. But, by modifying $R_G^1$, we can ensure that the quotient result is always a word. First, let us show that the previous theorem holds if we replace $R_G^1 = A(B\Delta^*R\Delta^*)^*\overline{B}$ by $R_G^2 = A(B\Delta^*R\Delta^*)^+\overline{B}$:

$$ 
\begin{align*}
L &= \{h_G(w) \setminus g_G(w) \mid w \in \mathcal{R}_G^1\} \cap T^* \\
&= (\{h_G(w) \setminus g_G(w) \mid w \in A(B\Delta^*R\Delta^*)^+\overline{B}\} \cap T^*) \\
&\quad \cup (\{h_G(\overline{A}\overline{B}) \setminus g_G(\overline{A}\overline{B})\} \cap T^*) \\
&= (\{h_G(w) \setminus g_G(w) \mid w \in A(B\Delta^*R\Delta^*)^+\overline{B}\} \cap T^*) \\
&\quad \cup (\{S\} \cap T^*) \\
&= \{h_G(w) \setminus g_G(w) \mid w \in \mathcal{R}_G^2\} \cap T^*
\end{align*}
$$

To ensure that all derivations will end with words, let's define the final rules $R_f$ as the rules of $R$ whose right-hand side is a word: $R_f = \{r_i : \alpha_i \to \beta_i \in R \mid \beta_i \in T^*\}$. Then, we can construct our new regular set $R_G^3 = A(B\Delta^*R\Delta^*)^*(BT^*R_fT^*)\overline{B}$. Let show that the intersection with $T^*$ is useless with this regular set by showing that $\forall w \in \mathcal{R}_G^3$, $h_G(w) \setminus g_G(w) \in T^*$.

Let $w \in \mathcal{R}_G^3$ and let $u, v \in T^*$ and $r : \alpha \to \beta \in R_f$ (so $\beta \in T^*$) such that $w \in A(B\Delta^*R\Delta^*)^*(Burv)\overline{B}$. As $h_G(w) \setminus g_G(w) = u\beta v \in T^*$, we can conclude that $\{h_G(w) \setminus g_G(w) \mid w \in \mathcal{R}_G^3\} \subseteq T^*$.

Remark that $\mathcal{R}_G^3 \subseteq \mathcal{R}_G^2$ since $T \subset \Delta$ and $R_f \subseteq R$. Therefore:

$$ \{h_G(w) \setminus g_G(w) \mid w \in \mathcal{R}_G^3\} \subseteq \{h_G(w) \setminus g_G(w) \mid w \in \mathcal{R}_G^2\} \cap T^* = L $$

What is left to prove is that $L \subseteq \{h_G(w) \setminus g_G(w) \mid w \in \mathcal{R}_G^3\}$. Let $w_G$ be a word of $L$. There exists $w \in \mathcal{R}_G^2$ such that $w_G = h_G(w) \setminus g_G(w)$. Let show that $w \in \mathcal{R}_G^3$. Let $u, v \in \Delta^*$, $r : \alpha \to \beta \in R$ such that $w = A(B\Delta^*R\Delta^*)^*(Burv)\overline{B}$. We know that $w_G = h_G(w) \setminus g_G(w) = u\beta v$. As $w_G$ is in $T^*$, $u\beta v$ is in $T^*$, so $u, v \in T^*$ and the right-side production of $r$ is in $T^*$, i.e., $r \in R_f$. Finally, we showed that $w \in \mathcal{R}_G^3$ and thus $w_G \in \{h_G(w) \setminus g_G(w) \mid w \in \mathcal{R}_G^3\}$.

We can therefore conclude that $L = \{h_G(w) \setminus g_G(w) \mid w \in \mathcal{R}_G^3\}$.

Let $G' = (N, T, R', S)$ such that $\alpha \to \beta \in R'$ iff $\alpha' \to \beta' \in R$, so $L(G') = L^r$. We use $G'$ to end up with the equation presented in the theorem:

$$ 
\begin{align*}
L &= (L^r) \\
&= \{h_{G'}(w) \setminus g_{G'}(w) \mid w \in \mathcal{R}_{G'}^3\}^r \\
&= \{m \mid h_{G'}(w)m = g_{G'}(w), w \in \mathcal{R}_{G'}^3\}^r \\
&= \{m^r \mid h_{G'}(w)m = g_{G'}(w), w \in \mathcal{R}_{G'}^3\} \\
&= \{m^r \mid m^r h_{G'}(w)^r = g_{G'}(w)^r, w \in \mathcal{R}_{G'}^3\} \\
&= \{g_{G'}(w)^r / h_{G'}(w)^r \mid w \in \mathcal{R}_{G'}^3\} \\
&= \{g_{G'}^r(w) / h_{G'}^r(w) \mid w \in (\mathcal{R}_{G'}^3)^r\}
\end{align*}
$$

where $g_{G'}^r$ and $h_{G'}^r$ are defined in Table 7. $\square$

We can now prove the main result.

**Theorem 6.27.** Let $n \ge 1$. A language $L$ is recursively enumerable if and only if there exists an LR(0) grammar $G$ such that $L \in \delta I^n(G)$.
<figure><img src="image_5.png" /><figcaption>Fig. 2. A summarized DPDA for the language $L_3$.</figcaption></figure>

**Proof.** This result is based on the previous Lemma. Let us show first the result for $n = 1$. Let $R \subseteq T^*$, $g: T \to T$ and $h: T \to T$ such that $L = \{g(w)/h(w) | w \in R\}$ as defined in the proof of Lemma 6.26. Our goal is to create a deterministic context-free grammar $G$ and a symbol $#$ such that its unexpected injection language $\delta I(G, #)$ is in the form $g(w)/h(w)$. To this end, we introduce three new languages, $L_1$, $L_2$ and $L_3$, defined over the symbols $T' = T \cup \{\#$, $\}$ as:

$$L_1 = \{w^r \#$ h(w) | w \in R\}$$

$$L_2 = \{w^r \$ g(w) | w \in R\}$$

$$L_3 = L_1 \cup L_2$$

Let's show that $L_3$ is a deterministic context-free language by constructing a deterministic pushdown automaton (DPDA) that recognizes it. Let $A_h$ be a deterministic finite-state automaton that recognizes the regular language $R^r$ and let modify it into $A'_h$ such that each symbol that is read is pushed to the stack. Let $A_g$ (resp. $A_h$) be a DPDA that recognizes $g(w)$ (resp. $h(w)$) by empty stack guided by the word $w^r$ that has already been pushed. More precisely, denote $q_g$ the initial state of $A_g$ and $A'_g$ the rest of the states of $A_g$.

During the processing of the word, we can detect the end of the regular expression when the symbol $\$$ (absent in $R$) occurs. The only tricky part is to choose which DPDA to use after $\$$, either $A_h$ or continuing with $A'_g$. It can be easily done thanks to the symbol $#$ since no word of $g(w)$ contains $#$ (cf. the form of $R$ and Table 6). Hence, if $#$ is encountered, we continue with $A_h$ and otherwise, we continue with $A_g$. A DPDA for $L_3$ can be built as shown in Fig. 2: the words of $L_3$ are accepted by empty stack.

Now that we know that $L_3$ is a deterministic context-free language, we examine its unexpected injection language at $\#$.

$$\delta I(G, \#) = \{m \in T'^* | \exists p, s \in T'^*, pms \in L_3, p\#s \in L(G)\} - E(G, \#) \quad (1)$$

$$= \{m \in T'^* | \exists w \in R, w^r \$ m h(w) \in L_3\} - \{\#\} \quad (2)$$

$$= \{w^r \$ m / h(w) | w \in R, m \in L_3\} - \{\#\} \quad (3)$$

$$= (\{w^r \$ m / h(w) | w \in R, m \in L_2\} \cup \{\#\}) - \{\#\} \quad (4)$$

$$= \{w^r \$ w_2^r \$ g(w_2) / h(w) | w, w_2 \in R\} \quad (5)$$

$$= \{g(w) / h(w) | w \in R\} \quad (6)$$

$$= L \quad (7)$$

Passing from line (1) to line (2) is justified by the fact that all the words in $L_3$ that contain $\#$ come from $L_1$ (since the words of $L_2$ cannot contain $\#$), so necessarily $p = w^r \$$ and $s = h(w)$ for any $w \in R$. Passing from line (3) to line (4) is justified by the fact that $\{w^r \$ m / h(w) | w \in R, m \in L_1\} = \{\#\}$. Passing from line (6) to line (7) is justified by the Lemma 6.26.

Finally, we constructed the deterministic context-free language $L_3$ with a deterministic grammar $G$ such that $\delta I(G, \#) = L$. So $L \in \delta I^1(G)$.

In fact, we can expand this theorem: first, the grammar $G$ we construct is in fact LR(0) and second, we can modify the proof to replace $\delta I^1(G)$ by any $\delta I^n(G)$ for a fixed value of $n \ge 1$.

This is a direct consequence of a result shown by [55]: LR(0) languages are exactly the languages recognized by a deterministic pushdown automaton that accepts by empty stack. This is the case of the automaton constructed in the previous proof, so $L_3$ is an LR(0) language. In fact, we can modify the construction of $L_1$ in the previous proof by replacing $\#$ with $\#$^n ($n$ times the symbol $\#$) and therefore get that $\delta I(G, \#$^n) = L$. So, for any $n \ge 1$, a language $L$ is recursively enumerable if and only if there exists an LR(0) grammar $G$ and $t \in \Delta^n$ such that $L = \delta I(G, t)$. $\square$

The undecidability of the intent-security is a corollary of the previous theorem and the fact that emptiness is undecidable for recursively enumerable languages.

**Corollary 6.28.** Let $G$ be an LR(0) grammar, $n \ge 1$. It is undecidable whether $G$ is intent-secure for intent length $n$.

**Proof.** Since the emptiness of recursively enumerable languages is undecidable, it is undecidable whether $\delta I(G, t) = \emptyset$ for any $t \in \Delta^+$. Therefore, it is undecidable whether $G$ is intent-secure for intent length $n$. $\square$

If the intent-security is undecidable for the class of LR(0) grammars, it is also undecidable for the classes that include LR(0) grammars, such as LR($k$) grammars, deterministic grammars and context-free grammars. We show a similar result for another subclass of context-free grammars: linear grammars.
**Theorem 6.29.** Let $n \ge 1$. A language $L$ is recursively enumerable if and only if there exists a linear grammar $G$ such that $L \in \delta I^n(G)$.

**Proof.** Let us show that we can construct a linear grammar $G$ for some recursively enumerable language $L$. As shown by Latteux and Turakainen [66] (Corollary 4), there exist two linear grammars $G_1 = (N_1, T, R_1, S_1)$ and $G_2 = (N_2, T, R_2, S_2)$ such as $L = L(G_2) \setminus L(G_1)$. Let us rewrite this quotient as the set of unexpected injections of a grammar $G$.

To this end, we will first modify $G_1$ to introduce a marker $\$$. First, let us introduce a fresh terminal $\$$, and let $h: T \cup \{\}$ $\to T$ be the homomorphism such that $h(\$) = \epsilon$ and otherwise $h(t) = t$ for all $t \in T$. Consider the language $L' = h^{-1}(L(G_1)) \cap (T^*ST^*) = \{w\$v | ww \in L(G_1)\}$. Because of the closure of linear languages for inverse homomorphism and intersection with a regular language, $L(G_1)$ is linear. Let $G'_1$ be a linear grammar for $L(G_1)$. Let $\#$ be a new symbol, and consider the linear grammar $G = (N_1 \cup N_2, T \cup \{\$, \#\}, R_1 \cup R_2 \cup \{S \to S_1, S \to S_2\#\}, S)$. Note that $L(G) = L(G'_1) \cup (L(G_2) \cdot \#\}$). We show that $\delta I(G, \#) = L(G_2) \setminus L(G_1)$. By definition of $G$, the only templates where $\#$ can appear are $\{(v\$, \epsilon) | v \in L(G_2)\}$. Then:

$$ 
\begin{aligned}
I(G, \#) &= \{w \in T^* | v\$w \in L(G), v \in L(G_2)\} \\
&= \{w \in T^* | v\$w \in L(G'_1), v \in L(G_2)\} \cup \{\#\} \\
&= \{w \in T^* | vw \in L(G_1), v \in L(G_2)\} \cup \{\#\} \\
&= (L(G_2) \setminus L(G_1)) \cup \{\#\}
\end{aligned}
$$

Since $\#$ is a terminal symbol, we have $E(G, \#) = \{\#\}$. Then:

$$ \delta I(G, \#) = I(G, \#) - E(G, \#) = L(G_2) \setminus L(G_1) = L $$

In fact, we can modify the construction of $G$ by replacing $\#$ with $\#$ and therefore get that $\delta I(G, \#$) = $L$. So, $L$ is recursively enumerable if and only if there exists a linear grammar $G$ such that $L \in \delta I^n(G)$. $\square$

**Corollary 6.30.** Let $G$ be a linear grammar, $n \ge 1$. It is undecidable whether $G$ is intent-secure for intent length $n$.

**Proof.** Same as Corollary 6.28. $\square$

These results show there is no automatic way of proving that some LR(0) or linear grammar is intent-secure. Since LR(0) are among the most simple deterministic grammars, it means that the vast majority of programming languages would be difficult to be proved intent-secure. For such languages, the static analysis of individual templates (discussed in Section 5) is a more promising approach.

The last result was shown for one blank. In the following, we show that infinite context-free languages are inherently intent-insecure for at least two blanks.

**Theorem 6.31.** Infinite context-free languages are inherently intent-insecure for at least two blanks.

**Proof.** Let $G$ be a context-free grammar that describes an infinite language. If $G$ describes a regular language, then according to Theorem 6.22 it is not intent-secure with a single blank, so it cannot be intent-secure with two blanks.

Let us assume that $G$ describes a non-regular language. As remarked by Chomsky in [50], $G$ must be self-embedding, which means there is a symbol $A \in N$ and $y, z \in T^+$ (so $y \ne \epsilon$ and $z \ne \epsilon$) such that $A \Rightarrow^* yAz$. Let denote $b$ the last terminal of $y$ and $c$ the first terminal of $z$. Let $\iota_1 = b$ and $\iota_2 = c$. Let $w_1, w_2 \in T^*$ such that $S \Rightarrow^* w_1Aw_2$. Let's define $p, s \in T^*$ such that $pb = w_1y$ and $cs = zw_2$. Then $S \Rightarrow^* w_1Aw_2 \Rightarrow^* w_1yAzw_2 = pbAcs$.

Let $w_A \in T^+$ such that $A \Rightarrow^* w_A$. Let consider the following template $p \rightarrow_1 w_A \rightarrow_2 s$ where the first (resp. second) blank is associated with the intent $b$ (resp. $c$). This template, filled with the intents, leads to $pbw_Acs$, a word in $L(G)$. Let consider the injection $(by, zc)$. Because $S \Rightarrow^* pbAcs$ and $pbAcs \Rightarrow^* pbyAzcs \Rightarrow^* pbyw_Azcs$, the latter is in $L(G)$. So $(by, zc) \in I(G, (b, c))$. This is illustrated by Fig. 3.

Since $y \ne \epsilon$ and $z \ne \epsilon$, $by \ne b$ and $zc \ne c$ so $(by, zc) \notin E((b, c)) = \{(b, c)\}$. Finally, we can conclude that $(by, zc) \in \delta I(G, (b, c))$, and therefore that $G$ is inherently intent-insecure with two blanks. Obviously, the same example can be carried out if there are more than two blanks. $\square$

<figure><img src="image_6.png" /><figcaption>(a) Simplified version of the parse tree of $pbw_Acs$</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>(b) Simplified version of the parse tree of $pbyw_Azcs$</figcaption></figure>

<caption>**Fig. 3.** Illustration of the proof of Theorem 6.31. Injections are in red. (For interpretation of the references to colour in this figure legend, the reader is referred to the web version of this article.)</caption>
<figure><img src="image_8.png" /><figcaption>Fig. 4. Parse tree for expected injections.</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Fig. 5. Parse tree for the injection attack.</figcaption></figure>

**Example 6.32.** The injection vulnerability stemming from the context-free pumping lemma is less prevalent because it requires two injection points. However, consider again this LDAP template: `(&{uid=—}) (passwd=—)` We can safely assume that the developer expects a string *s* into each injection point, leading to the parse tree presented in Fig. 4.

If the injection in the first blank is `admin`) `!(&{1=0` and the injection in the second blank is `text`)), then the final query is: `(&{uid=admin}) `!(&{1=0}(passwd=text)))` where the injections are in red to improve readability. This classical LDAP injection bypasses the password check by pumping the *S* nonterminal, as shown in Fig. 5. Sadly, there is no way to avoid this kind of vulnerabilities without leaving the context-free language class.

Such recursive structure is ubiquitous in many languages. This theorem shows that if there is a blank on both side of such recursive structure in a template, then it is not safe. As an example, the simple intent-secure language for one blank proposed in Proposition 6.9 (`((a^n cdb^n | n ≥ 0))`) is vulnerable with two blanks: in the template `a—_1 acdb—_2 b`, where the intent is `a` for `—_1` and `b` for `—_2`, the injection `(aa,bb)` is valid as well.

We can conclude that the only context-free grammars that are intent-secure with at least two blanks are finite languages. This fact is important to consider when designing a new network protocol. For example: dealing with size-bounded messages (or adding context-sensitive fields such as payload length) is a necessary measure for injection-vulnerability-free protocols. We expect context-sensitive languages to allow for stronger intent-security guarantees, but this question is out of the scope of our study.

## 7. Characterization of unexpected injections

We presented in the previous sections two security properties: the intent-equivalence of a template and the intent-security of a grammar. Another type of result we are interested in is the characterization of the set of unexpected injections for whole classes of grammars. So we define the set of unexpected injections on a set of grammars as the union of all grammars and intent length.

**Definition 7.1** (Unexpected injections on a set of grammars). Let *C* be a set of grammars. We define the set of languages of unexpected injections on *C* as:

$$ \delta I(C) = \bigcup_{G \in C} \bigcup_{n>0} \delta I^n(G) $$
First, we show that we can characterize the set of unexpected injections of regular languages: a grammar is regular if and only if it can be expressed as the set of unexpected injections of a regular grammar.

**Theorem 7.2.** REGL = δI(REGG)

**Proof.** Let us first show that REGL ⊆ δI(REGG). Let L be a regular language and G = (N, T, R, S) a regular grammar of L. Let G' = (N ∪ {S'}, T ∪ {#}, R ∪ {S' → S, S' → #}, S'). G' is a regular grammar. Remark that L(G') = L ∪ {#}. Then I(G', #) = L ∪ {#} and E(G', #) = {#}, so L = I(G', #) − E(G', #) = δI(G', #). So REGL ⊆ δI(REGG).

Let G = (N, T, R, S) be a regular grammar and t ∈ Δⁿ. Let us show that δI(G, t) is regular. Let us consider two cases: t contains at least one nonterminal and t ∈ Tⁿ. Recall that δI(G, t) = I(G, t) − E(G, t). The language E(G, t) is regular and set difference is closed for regular language. Thus, to prove that δI(G, t) is regular, we only need to prove that I(G, t) is regular.

In the first case, t contains at least one nonterminal. Due to the form of the rules in the regular grammar, every sentential form derivable from S is either in T* or in T* × N. Thus, t ∈ T* × N and all templates where t can appear have an empty suffix. Let us construct the regular grammar G' that describes the set of sentential form of G: G' = (T ∪ {A' | A ∈ N}, N, R ∪ {A → A' | A ∈ N}, S). So G' = {α | α ∈ Δ*: S ⇒*α}. Due to the form of its rules, G' is regular.

By definition, I(G, t) = {w ∈ T* | ∃p, s ∈ T*: pws ∈ L(G) and S ⇒* pts}. However, we know that the suffix is empty so I(G, t) = {w ∈ T* | ∃p ∈ T*: pw ∈ L(G) and S ⇒* pt}. Let P = L(G')/t the prefixes of sentential forms of G that end with t. Thus, I(G, t) = {w ∈ T* | ∃p ∈ P : pw ∈ L(G)} = P \ L(G) = (L(G')/t) \ L(G). This quotient leads to a regular language. Finally, I(G, t) is regular.

In the second case, t ∈ Tⁿ. For every (p, s) such as S ⇒* pts, F(L, (p, s)) is regular. We will show that I(G, t) = ⋃_{[(p,s)]S→^{pts}} F(L, (p, s)) is in fact a finite union and therefore that I(G, t) is regular. Denote A a deterministic finite state machine with k states that recognizes L(G). After reading the prefix p, A can be in one of k states. Denote this state S_{start}(p). For any s, there exist none, one or multiple states from which reading s lead to a final state. Denote this set of states S_{end}(s).

Let us prove that for any (p, s), (p', s') such as S_{start}(p) = S_{start}(p') and S_{end}(s) = S_{end}(s'), we have F(L, (p, s)) = F(L, (p', s')). Let A_{(p,s)} be the same automata as A with the difference that its initial state S_{start}(p) and its finale states are S_{end}(s). We define in a similar fashion A_{(p',s')}. Then w ∈ F(L, (p, s)) if and only if pws is recognizable from A. In that case, after reading p, A is in state S_{start}(p) and after reading w, it is in one of the state of S_{end}(s). So A_{(p,s)} recognizes w. If S_{start}(p) = S_{start}(p') and S_{end}(s) = S_{end}(s'), then A_{(p',s')} = A_{(p,s)} and so A_{(p',s')} recognizes w as well. Therefore w ∈ F(L, (p', s')). So F(L, (p, s)) = F(L, (p', s')). It means that I(G, t) is a finite union (of at most k2k sets) of regular languages, so I(G, t) is regular.

Finally, in both cases, δI(G, t) = I(G, t) − E(G, t) is regular so δI(REGG) ⊆ REGL.

Finally, REGL = δI(REGG). □

Based on the results from the last subsection, we can also show that any recursively enumerable language can be expressed as the set of unexpected injection of an LR(0) grammar.

**Theorem 7.3.** RE = δI(LR(0))

**Proof.** Let us first prove that δI(CFG) ⊆ RE. For any G ∈ CFG, n ≥ 0 and t ∈ Δⁿ, the following equality is verified: δI(G, t) = I(G, t) − E(G, t).

Let us first show that I(G, t) is recursively enumerable. Let w ∈ Tⁿ. There exists an algorithm that halts when w ∈ I(G, t) : one can iterate over all templates (p, s) ∈ (Tⁿ)² and verify whether S ⇒* pts and S ⇒* pws (this is decidable because G is context-free). Therefore I(G, t) is recursively enumerable.

Because G is a context-free grammar, E(G, t) is also a context-free language recognized by the grammar G' = (N ∪ {S'}, T, R ∪ {S' → t}, S'), with S' a new nonterminal. It means in particular that E(G, t) is a decidable language and therefore that Ē(G, t) is also decidable, hence recursively enumerable.

Finally, δI(G, t) = I(G, t) − E(G, t) = I(G, t) ∩ Ē(G, t) is the intersection of two recursively enumerable languages and is therefore itself a recursively enumerable language. So δI(CFG) ⊆ RE. Besides, δI(LR(0)) ⊆ δI(CFG) (Theorem 6.17) so RE ⊇ δI(LR(0)).

Let prove that RE ⊆ δI(LR(0)). Let L ∈ RE and n ≥ 0. Due to Theorem 6.27, there exists an LR(0) grammar G such as L ∈ δI¹(G). So L ∈ δI(LR(0)). Therefore, RE ⊆ δI(LR(0)).

Finally, RE = δI(LR(0)). □

**Theorem 7.4.** RE = δI(LinG)

**Proof.** The proof is similar to the previous one but relies on Theorem 6.29 instead. □

This concludes our analysis of intent-equivalence, intent-security and unexpected injections characterization.

## 8. Conclusion

Injections are among the most common threats to online services. Even if countermeasures exist, there is no guarantee that a developer will always have the knowledge or time to implement them sufficiently, if they are aware of the problem at all. Furthermore, to the best of our knowledge, no research has been done on protections embedded in the language itself.

In this paper, we formalized the notions of intent-secure grammar and intent-equivalent query. If a grammar is intent-secure, the developer is sure that only expected injections (according to their intent) can lead to grammatically correct sentences, as long as their intent consists of a single symbol (terminal or not). This property is very strong since the developers do not have to specify their
<figure><img src="image_10.png" /><figcaption>Fig. 6. Language inclusion.</figcaption></figure>

<table><caption>**Table 8**

Intent-equivalence property. D: decidable. U: undecidable. ?: unknown.</caption><thead><tr><th></th><th></th><th>One or more blanks [-1 em]<sub>t</sub> ∈ (Δ<sup>+</sup>)<sup>m</sup></th><th>One or more blanks [-1 em]<sub>t</sub> ∈ (Δ<sup>+</sup>)<sup>m</sup></th><th>One or more blanks [-1 em]<sub>t</sub> ∈ (T<sup>+</sup>)<sup>m</sup></th></tr></thead><tbody><tr><td>REGG</td><td>D</td><td>(Th. 5.14)</td><td>D</td><td>(Th. 5.22)</td></tr><tr><td>VPG</td><td>D</td><td>(Th. 5.19)</td><td>D</td><td>(Th. 5.22)</td></tr><tr><td>LR(0)</td><td>D</td><td>(Th. 5.17)</td><td>D</td><td>(Th. 5.22)</td></tr><tr><td>LR(k)</td><td>D</td><td>(Th. 5.16)</td><td>?</td><td>(Th. 5.22)</td></tr><tr><td>LinG</td><td>U</td><td>(Th. 5.20)</td><td>U</td><td>(Th. 5.22)</td></tr><tr><td>CFG</td><td>U</td><td>(Co. 5.21)</td><td>U</td><td>(Th. 5.22)</td></tr></tbody></table>

<table><caption>**Table 9**

Intent-security property. F: always false. D: decidable. U: undecidable.</caption><thead><tr><th></th><th>One blank</th><th>Two or more blanks</th></tr></thead><tbody><tr><td>Finite, |L| ≥ 2</td><td>D (Pr. 6.21)</td><td>D (Pr. 6.21)</td></tr><tr><td>REGG with infinite language</td><td>F (Th. 6.22)</td><td>F (Th. 6.22)</td></tr><tr><td>Context-free grammars with [-1 em]infinite regular sublanguage</td><td>F (Co. 6.23)</td><td>F (Th. 6.31)</td></tr><tr><td>LR(0) with infinite language</td><td>U (Co. 6.28)</td><td>F (Th. 6.31)</td></tr><tr><td>LinG with infinite language</td><td>U (Co. 6.30)</td><td>F (Th. 6.31)</td></tr><tr><td>CFG with infinite language</td><td>U (Co. 6.28)</td><td>F (Th. 6.31)</td></tr></tbody></table>

intent: they do not have to be an expert in the grammar of the languages they use. As a “sanity check”, we applied our definition to well-known language to show that they are indeed inherently intent-insecure. Besides, we showed as well that infinite intent-secure languages do exist.

However, such property is not easy to obtain. The results on unexpected injection languages are closely related to the $\delta I(C)$ sets, whose relationships are summarized in Fig. 6. Grammars of finite languages are easy to prove to be intent-secure. Infinite regular languages (and their supersets) are inherently insecure. The languages of unexpected injections of LR(0) and linear grammars are exactly the recursively enumerable languages and thus the intent-secure property of a deterministic grammar is undecidable. Furthermore, every infinite context-free language is vulnerable with multiple blanks. The intent-equivalence for a given query is also undecidable for context-free grammars but, fortunately, it is decidable for LR(0) grammars and visibly-pushdown grammars (for all intent) and LR(k) grammars (for intents of length 1). Decidability results on intent-equivalence are summarized in Table 8 and results on intent-security are summarized in Table 9.

Thus, these results open up many theoretical possibilities and technical implications. In the following, we identify some of them, including the ones presented in the introduction.

**Q1: Does string concatenation necessarily lead to injection vulnerabilities?** String concatenation is generally recognized as a major source of injection vulnerabilities [2]. Popular protections like prepared statements aim to prevent the developer from directly performing such concatenation. Our study is another proof that string concatenation can indeed easily bring injection vulnerabilities. However, we also showed that string concatenation with only one user input does not necessarily lead to injection vulnerabilities as even complex grammars can be intent-secure (Corollary 6.28).

**Q2: Could a skilled developer write only secure queries?** Injection vulnerabilities are often considered to stem from bad programming practices. This reasoning implicitly assumes that a skilled developer could always write secure queries, or at least verify that their queries are not vulnerable to injection-based attacks. Such a position is notably supported in the testing community [67]: “data validation is the first line of defense against a hostile world”. However, Theorems 6.27 and 7.3 and the Corollary 6.28 show that malicious injections may be very hard to detect. Moreover, languages with intricate unexpected injections are not necessarily exotic or unsuitable for computer science, as shown by the Proposition 6.25. This proposition considers an LL(1) language with an XML-like structure whose language of unexpected injections for some intent is context-sensitive. It shows that the injection vulnerabilities are embedded in the language itself and that one cannot rely on just the developer’s skills to avoid them. If one uses an intent-insecure grammar, additional security mechanisms, such as filtering, input sanitization, static analysis, or intrusion detection, are essential.

**Q3: Is a simpler language always more secure than a more complex one?** It is generally believed that simpler languages are less prone to being attacked, as explained in [68]: “a complex computational system is an engine for executing malicious computer
programs delivered in the form of crafted input”. We confirmed the classic observation that a language subset is at least as secure as the whole language (Theorem 6.17). Simple languages are very useful as the intent-security and intent-equivalence of finite languages is decidable (Proposition 6.21). However, we would like to add some nuance to that statement: we also showed that a complex language is not necessarily less safe than a simpler language. For example, all infinite regular languages are intent-insecure (Theorem 6.22), while context-free languages may be intent-secure (Proposition 6.9). Furthermore, context-free languages are inherently intent-insecure with two blanks.

**Q4: Why do (nearly) all computer languages contain injection vulnerabilities?** As shown by Corollary 6.23, every language that is a superset of an infinite regular language is inherently intent-insecure for a simple intent. This result has great significance, as programming languages almost always include such regular patterns: SQL includes the infinite regular language SELECT (column,)* column FROM table WHERE condition while programming and scripting languages generally accept statement lists in the form (statement;)* statement. Arithmetic and Boolean expression generally include infinite regular languages as well, e.g. (3 +)* 5 and (b OR)* b. This kind of regular structure is widely used because of its simplicity but allows for injection attacks. It would undoubtedly be challenging to replace these structures with non-regular patterns while still retaining their simplicity for the developers. But even in the absence of such patterns, it is impossible to avoid injection vulnerabilities in some queries with two blanks in usual computer languages without any additional security mechanisms, as confirmed by the Theorem 6.31.

This theory highlights limitations in existing security approaches and could lead to new security strategies. The performances of today's IDS results either from a learning phase that identifies typical benign queries (in the case of behavioral IDS) or from the signatures of typical injections such as the infamous ' or '1'='1. However, they rarely leverage the formal grammar that describes the language, causing non-zero false positive rate (i.e., some alerts don't correspond to attacks) and false negative rate (i.e., some attacks are not detected). Our study shows that the concept of developer intent could lead to better, provable protections.

Besides, knowing their intent, a developer could better test injections rather than relying on hazy pattern-matching. For example, they can use a parser to check if their intent derives the user input (Proposition 5.4). This strategy is also valid for several blanks. A protection system could automatically support this test if the developer's intent is known. It would behave similarly to prepared statements in SQL. However, in prepared statements, the developer is limited to some terminals while this system could support any intent, simple or complex, including non-terminals. Besides, such a system would be applicable to any context-free grammar and not only to SQL.

Finally, an intent analysis could be performed to ensure whether these tests are necessary (Theorems 5.14, 5.17 and 5.16) for most grammars used to date (regular, LR(0), and LR(*k*) in particular). Sadly, this test is not possible for linear and more complex grammars (Theorem 5.21). This last point is problematic because computing performance increases incentives for developers to use more general grammar parsers. For example, the lexical grammar of the Rust language is not context-free because of its raw strings<fnref n="6" />, neither is the syntax of the Python language because of its semantic indentation.

Based on our results and the previous discussion, we propose a set of research directions that could both extend this present work and propose new security tools.

* An analysis of popular programming languages may identify some intents for which the language is intent-secure. One can distinguish data tokens (such as strings, identifiers, etc.) that can typically contain user data from control tokens (keywords such as function, SELECT, <title>, etc. and symbols such as {, [, (, etc.) that are typically written by the developer only and not filled by the user. Pragmatically, a query language does not have to be intent-secure for every symbol but only for data tokens.

* At the moment, our theory is adapted to context-free grammars. However, most network protocol languages are regular with contextual fields (such as CRC values and message length). A focus on this class could bring new results for their risk analysis. Indeed, all contextual fields are not as useful against injections: adding a message length, for example, does not make the grammar classes much more complicated [69].

* Given the developer intent and the user input, it is easy to verify whether the injection is expected or not. This intent could be inferred from unit tests, or by statically analyzing the templates of LR(*k*) grammars (if the intent length is 1). In both cases, it would be easy to verify user inputs with respect to the inferred developer intent.

## CRediT authorship contribution statement

Eric Alata: Conceptualization, Formal analysis, Methodology, Writing – original draft; Pierre-François Gimenez: Conceptualization, Formal analysis, Methodology, Writing – original draft.

## Data availability

No data was used for the research described in the article.

## Declaration of competing interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

<footnote n="6">⁶ https://github.com/rust-lang/rust/blob/0.12.0/src/grammar/raw-string-literal-ambiguity.md</footnote>
## References

[1] J. Forristal, NT Web Technology Vulnerabilities, 1998, Accessed: 2022-06-08, http://phrack.org/issues/54/8.html.

[2] E. Poll, LangSec revisited: input security flaws of the second kind, in: 2018 IEEE Security and Privacy Workshops (SPW), IEEE, 2018, pp. 329–334.

[3] CWE, 2021 CWE Top 25 Most Dangerous Software Errors, 2021, Accessed: 2022-06-08, https://cwe.mitre.org/top25/archive/2021/2021_cwe_top25.html.

[4] OWASP, The Ten Most Critical Web Application Security Risks, 2017, Accessed: 2022-06-08, https://owasp.org/www-pdf-archive/OWASP_Top_10-2017-%28en%29.pdf.pdf.

[5] OWASP, The Ten Most Critical Web Application Security Risks, 2021, Accessed: 2022-06-08, https://owasp.org/Top10/#welcome-to-the-owasp-top-10-2021.

[6] P. Bisht, P. Madhusudan, V.N. Venkatakrishnan, CANDID: dynamic candidate evaluations for automatic prevention of SQL injection attacks, ACM Trans. Inf. Syst. Secur. 13 (2) (2010) 14. https://doi.org/10.1145/1698750.1698754

[7] E. Alata, P.-F. Gimenez, Towards programming languages free of injection-based vulnerabilities by design, in: 2025 IEEE Security and Privacy Workshops (SPW), San Francisco CA, United States, 2025, pp. 1–17. https://hal.science/hal-05079251.

[8] D.E. Denning, An intrusion-detection model, IEEE Trans. Softw. Eng. SE-13 (2) (1987) 222–232.

[9] B. Miller, L. Fredriksen, B. So, An empirical study of the reliability of UNIX utilities, Commun. ACM 33 (12) (1990) 32–44. https://doi.org/10.1145/96267.96279

[10] A. Doupé, M. Cova, G. Vigna, Why johnny can't pentest: an analysis of black-box web vulnerability scanners, in: C. Kreibich, M. Jahnke (Eds.), Detection of Intrusions and Malware, and Vulnerability Assessment, 6201 of *Lecture Notes in Computer Science*, Springer Berlin Heidelberg, Berlin, Heidelberg, 2010, pp. 111–131. https://doi.org/10.1007/978-3-642-14215-4-7

[11] J. Fonseca, M. Vieira, H. Madeira, Testing and comparing web vulnerability scanning tools for SQL injection and XSS attacks, in: 13th Pacific Rim International Symposium on Dependable Computing, IEEE, Melbourne, Victoria, Australia, 2007, pp. 365–372. https://doi.org/10.1109/PRDC.2007.55

[12] A. Dessiatnikoff, R. Akrout, E. Alata, M. Kaăniche, V. Nicomette, A clustering approach for web vulnerabilities detection, in: 17th Pacific Rim International Symposium on Dependable Computing, IEEE, Pasadena, CA, USA, 2011, pp. 194–203. https://doi.org/10.1109/PRDC.2011.31

[13] R. Akrout, E. Alata, M. Kaăniche, V. Nicomette, An automated black box approach for web vulnerability identification and attack scenario generation, J. Braz. Comput. Soc. 20 (1) (2014) 4:1–4:16. https://doi.org/10.1186/1678-4804-20-4

[14] M.-T. Trinh, D.-H. Chu, J. Jaffar, S3: a symbolic string solver for vulnerability detection in web applications, in: Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, ACM, New York, NY, USA, 2014, pp. 1232–1243. https://doi.org/10.1145/2660267.2660372

[15] F. Yu, M. Alkhalaf, T. Bultan, O.H. Ibarra, Automata-based symbolic string analysis for vulnerability detection, Formal Methods Syst. Des. 44 (1) (2014) 44–70. https://doi.org/10.1007/s10703-013-0189-1

[16] K. Elshazly, Y. Fouad, M. Saleh, A. Sewisy, A survey of SQL injection attack detection and prevention, J. Comput. Commun. 2 (08) (2014) 1. https://doi.org/10.4236/jcc.2014.28001

[17] H. Dehariya, P.K. Shukla, M. Ahirwar, A survey on detection and prevention techniques of SQL injection attacks, Int. J. Comput. Appl. 137 (5) (2016) 9–15. https://doi.org/10.5120/ijca2016908672

[18] S.M.H. Chaki, M.M. Din, A survey on SQL injection prevention methods, Int. J. Innov. Comput. 9 (1) (2019) 47–54. https://doi.org/10.11113/ijic.v9n1.224

[19] G. Deepa, P.S. Thilagam, Securing web applications from injection and logic vulnerabilities, Inf. Softw. Technol. 74 (C) (2016) 160–180. https://doi.org/10.1016/j.infsoft.2016.02.005

[20] Z. Su, G. Wassermann, The essence of command injection attacks in web applications, SIGPLAN Not. 41 (1) (2006) 372–382. https://doi.org/10.1145/1111320.1111070

[21] M.R. Islam, M.S. Islam, Z. Ahmed, A. Iqbal, R. Shahriyari, Automatic detection of NoSQL injection using supervised learning, in: V. Getov, J. Gaudiot, N. Yamai, S. Cimato, J.M. Chang, Y. Teranishi, J. Yang, H.V. Leong, H. Shahriar, M. Takemoto, D. Towey, H. Takakura, A. Elçi, S. Takeuchi, S. Puri (Eds.), 43rd IEEE Annual Computer Software and Applications Conference, COMPSAC 2019, Milwaukee, WI, USA, July 15–19, 2019, Volume 1, IEEE, 2019, pp. 760–769. https://doi.org/10.1109/COMPSAC.2019.00113

[22] B. Hou, Y. Shi, K. Qian, L. Tao, Towards analyzing mongoDB NoSQL security and designing injection defense solution, in: 2017 IEEE 3rd International Conference on Big Data Security on Cloud (bigdatasetsecurity), IEEE International Conference on High Performance and Smart Computing (hpsc), and IEEE International Conference on Intelligent Data and Security (ids), 2017, pp. 90–95. https://doi.org/10.1109/BigDataSecurity.2017.29

[23] M. Liu, B. Zhang, W. Chen, X. Zhang, A survey of exploitation and detection methods of XSS vulnerabilities, IEEE Access 7 (2019) 182004–182016. https://doi.org/10.1109/ACCESS.2019.2960449

[24] M. Baykara, S. Güçlü, Applications for detecting XSS attacks on different web platforms, in: 2018 6th International Symposium on Digital Forensic and Security (ISDFS), 2018, pp. 1–6. https://doi.org/10.1109/ISDFS.2018.8355367

[25] N.M. Sheykhkanloo, A learning-based neural network model for the detection and classification of SQL injection attacks, Int. J. Cyber Warf. Terror. 7 (2) (2017) 16–41. https://doi.org/10.4018/IJCWWT.2017040102

[26] R. Jahanshahi, A. Doupé, M. Egele, You shall not pass: mitigating SQL injection attacks on legacy web applications, in: Proceedings of the 15th ACM Asia Conference on Computer and Communications Security, 2020, pp. 445–457.

[27] S. Son, K.S. McKinley, V. Shmatikov, Diglossia: detecting code injection attacks with precision and efficiency, in: Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security, 2013, pp. 1181–1192.

[28] W.G.J. Halfond, A. Orso, AMNESIA: analysis and monitoring for neutralizing SQL-injection attacks, in: Proceedings of the 20th IEEE/ACM international Conference on Automated software engineering, ASE '05, Association for Computing Machinery, New York, NY, USA, 2005, pp. 174–183. https://doi.org/10.1145/1101908.1101935

[29] W. Halfond, A. Orso, P. Manolios, WASP: Protecting web applications using positive tainting and syntax-aware evaluation, IEEE Trans. Softw. Eng. 34 (1) (2008) 65–81.

[30] O.C. Abikoye, A. Abubakar, A.H. Dokoro, O.N. Akande, A.A. Kayode, A novel technique to prevent SQL injection and cross-site scripting attacks using Knuth-Morris-Pratt string match algorithm, EURASIP J. Inf. Secur. 2020 (1) (2020) 1–14.

[31] A. Pramod, A. Ghosh, A. Mohan, M. Shrivastava, R. Shettar, SQLI detection system for a safer web application, in: 2015 IEEE International Advance Computing Conference (IACC), IEEE, 2015, pp. 237–240.

[32] M. Hoschele, A. Zeller, Mining input grammars with AUTOGRAM, in: 2017 IEEE/ACM 39th International Conference on Software Engineering Companion (ICSE-C), IEEE, 2017, pp. 31–34.

[33] H. Gu, J. Zhang, T. Liu, M. Hu, J. Zhou, T. Wei, M. Chen, DIAVA: a traffic-based framework for detection of SQL injection attacks and vulnerability analysis of leaked data, IEEE Trans. Reliab. 69 (1) (2019) 188–202.

[34] K.K. Mookhey, N. Burghate, Detection of SQL injection and cross-site scripting attacks, Symantec Security Focus (2004).

[35] M. Wan, K. Liu, An improved eliminating SQL injection attacks based regular expressions matching, in: 2012 International Conference on Control Engineering and Communication Technology, IEEE, 2012, pp. 210–212.

[36] A. Sravanthi, K.J. Devi, K.S. Reddy, A. Indira, V.S. Kumar, Detecting SQL injections from web applications, Int. J. Eng. Sci. Adv. Technol. 2 (3) (2012).

[37] B. Kranthikumar, R.L. Velusamy, SQL injection detection using REGEX classifier, J. Xi'an Univer. Arch. Technol. 12 (6) (2020) 800–809.

[38] S. Steiner, D.C. de Leon, J. Alves-Foss, A structured analysis of SQL injection runtime mitigation techniques, in: T. Bui (Ed.), 50th Hawaii International Conference on System Sciences, HICSS 2017, Hilton Waikoloa Village, Hawaii, USA, January 4–7, 2017, ScholarSpace / AIS Electronic Library (AISel), 2017, pp. 1–9. http://hdl.handle.net/10125/41505.

[39] A. Liu, Y. Yuan, D. Wijesekera, A. Stavrou, SQLProb: a proxy-based architecture towards preventing SQL injection attacks, in: Proceedings of the 2009 ACM Symposium on Applied Computing, SAC '09, Association for Computing Machinery, New York, NY, USA, 2009, pp. 2054–2061. https://doi.org/10.1145/1529282.1529737

[40] S.W. Boyd, A.D. Keromytis, SQLrand: preventing SQL injection attacks, in: M. Jakobsson, M. Yung, J. Zhou (Eds.), International Conference on Applied Cryptography and Network Security, Springer, Berlin, Heidelberg, 2004, pp. 292–302.
[41] D. Ray, J. Ligatti, Defining code-injection attacks, in: Proceedings of the 39th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL'12, ACM, New York, NY, USA, 2012, pp. 179-190. https://doi.org/10.1145/2103656.2103678

[42] R. Hansen, M. Patterson, Stopping injection attacks with computational theory, 2005, https://www.blackhat.com/presentations/bh-usa-05/bh-us-05-hansen.pdf.

[43] R.J. Hansen, M.L. Patterson, Guns and butter: towards formal axioms of input validation, 2005.

[44] L. Sassaman, M.L. Patterson, S. Bratus, M.E. Locasto, Security applications of formal language theory, IEEE Syst. J. 7 (3) (2013) 489-500.

[45] T. Bieschke, L. Hermerschmidt, B. Rumpe, P. Stanchev, Eliminating input-based attacks by dderiving automated encoders and decoders from context-free grammars, in: 2017 IEEE Security and Privacy Workshops (SPW), IEEE, 2017, pp. 93-101.

[46] J. Bangert, N. Zeldovich, Nail: a practical tool for parsing and generating data formats, in: 11th USENIX Symposium on Operating Systems Design and Implementation (OSDI 14), 2014, pp. 615-628.

[47] D. Kurilova, A. Potanin, J. Aldrich, Wyvern: impacting software security via programming language design, in: Proceedings of the 5th Workshop on Evaluation and Usability of Programming Languages and Tools, 2014, pp. 57-58.

[48] F. Momot, S. Bratus, S.M. Hallberg, M.L. Patterson, The seven turrets of babel: a taxonomy of langsec errors and how to expunge them, in: 2016 IEEE Cybersecurity Development (SecDev), IEEE, 2016, pp. 45-52.

[49] T. Dullien, Weird machines, exploitability, and provable unexploitability, IEEE Trans. Emerg. Top. Comput. 8 (2) (2017) 391-403.

[50] N. Chomsky, On certain formal properties of grammars, Inf. Contr. 2 (2) (1959) 137-167. https://doi.org/10.1016/S0019-9958(59)90362-6

[51] P.S. Landweber, Decision problems of phrase-structure grammars, IEEE Trans. Electron. Comput. EC-13 (4) (1964) 354-362.

[52] J.E. Hopcroft, J.D. Ullman, Formal Languages and their Relation to Automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1969. https://doi.org/10.1137/1012073

[53] S. Ginsburg, E.H. Spanier, Quotients of context-free languages, J. ACM 10 (4) (1963) 487-492. https://doi.org/10.1145/321186.321191

[54] S. Ginsburg, S.A. Greibach, Deterministic context free languages, Inf. Contr. 9 (6) (1966) 620-648. https://doi.org/10.1016/S0019-9958(66)80019-0

[55] D.E. Knuth, On the translation of languages from left to right, Inf. Contr. 8 (6) (1965) 607-639. https://doi.org/10.1016/S0019-9958(65)90426-2

[56] M.M. Geller, M.A. Harrison, On LR(k) grammars and languages, Theor. Comput. Sci. 4 (3) (1977) 245-276. https://doi.org/10.1016/0304-3975(77)90013-5

[57] R. Alur, P. Madhusudan, Visibly pushdown languages, in: Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, STOC '04, Association for Computing Machinery, New York, NY, USA, 2004, p. 202-211. https://doi.org/10.1145/1007352.1007390

[58] G. Rozenberg, A. Salomaa (Eds.), Handbook of formal languages, 1, Word, Language, Grammar, 1997.

[59] P.R.J. Asveld, A. Nijholt, The inclusion problem for some subclasses of context-free languages, Theor. Comput. Sci. 230 (1-2) (2000) 247-256.

[60] D.J. Rosenkrantz, R.E. Stearns, Properties of deterministic top-down grammars, Inf. Contr. 17 (3) (1970) 226-256.

[61] T. Kasami, An Efficient Recognition and Syntax Analysis Algorithm for Context-Free Languages, Technical Report R-257, Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, 1966.

[62] G. Sénizergues, The equivalence problem for deterministic pushdown automata is decidable, in: P. Degano, R. Gorrieri, A. Marchetti-Spaccamela (Eds.), International Colloquium on Automata, Languages, and Programming, Springer, Berlin, Heidelberg, 1997, pp. 671-681. https://doi.org/10.1007/3-540-63165-8_221

[63] A. Yehudai, The decidability of equivalence for a family of linear grammars, Inf. Contr. 47 (2) (1980) 122-136.

[64] B.S. Baker, R.V. Book, Reversal-bounded multipushdown machines, J. Comput. Syst. Sci. 8 (3) (1974) 315-332.

[65] J. Berstel, L. Boasson, Formal properties of XML grammars and languages, Acta Inf. 38 (9) (2002) 649-671.

[66] M. Latteux, P. Turakainen, On characterizations of recursively enumerable languages, Acta Inf. 28 (2) (1990) 179-186. https://doi.org/10.1007/BF01237236

[67] B. Beizer, Software Testing Techniques, Dreamtech Press, 2003.

[68] G. Hoglund, G. McGraw, Exploiting Software: How to Break Code, Pearson Education India, 2004.

[69] S. Lucks, N.M. Grosch, J. König, Taming the length field in binary data: calc-regular languages, in: 2017 IEEE Security and Privacy Workshops (SPW), IEEE, 2017, pp. 66-79.