\section{Introduction}

To communicate securely, the web increasingly adopts transport encryption via TLS~\cite{felt2017measuring}.
Nowadays, more than 75\% of all web requests are protected using TLS encryption~\cite{HTTP_Archive}.
This practice benefits communication security, but leads to additional performance penalties.
Most web transactions are short transfers that are significantly delayed by the TLS connection establishment.

To accelerate the connection establishment, TLS~1.3~\cite{rfc8446} and its predecessors provide session resumption mechanisms.
They abbreviate the TLS handshake based on a shared secret exchanged during a prior TLS session between the client and server.
In total, these resumption handshakes significantly reduce computational overhead for cryptographic operations and save up to one round-trip between client and server.

Load balancing can make it necessary to provide the content of a hostname via different servers.
To sustain the benefits of TLS resumptions in such a setup, the respective servers can share their secret TLS state related to the client's connection.
Furthermore, TLS~1.3~\cite{rfc8446} allows resumption handshakes across hostnames when they share the same TLS certificate.
Thus, the client can resume a previous connection to hostname $\mathcal{A}$ with hostname $\mathcal{B}$.
However, TLS~1.3~\cite{rfc8446} recommends not to use TLS resumption across hostnames.
We find that this recommendation of TLS~1.3 leads to a significant performance limitation.

As an illustration for such a performance limitation, we assume a website served from the hostname \textit{www.example.com}.
Moreover, we assume that the hostname \textit{example.com} is operated by the same entity and provides a redirect to \textit{www.example.com}.
A client that retrieves the website via the hostname \textit{example.com} thus needs to establish two TLS connections.
Following the specification of TLS~1.3, the client is required to establish both connections with two full handshakes.
However, as both hostnames are operated by the same entity we assume that they can share their secret TLS state with each other.
Thus, a performance optimized website retrieval requires only a full handshake to \textit{example.com} and subsequently conducts a resumption handshake to connect to \textit{www.example.com}.

In this work, we propose and evaluate a TLS extension that aims to enable the client to efficiently resume TLS connections across hostnames.
In summary, this paper makes the following contributions:
\begin{itemize}
\item we introduce a TLS extension that enables the efficient use of resumption handshakes across different hostnames.
\item we simulate the loading behavior of popular websites to assess the performance impact of our proposal.
Our results indicate, that our approach can convert about 58.7\% of the required full TLS handshakes to performance optimized resumption handshakes upon the first visit of an average website.
This reduces the computational costs for the respective TLS handshakes by about 44\% and accelerates the establishment of TLS~1.3 connections by up to 30.6\%.
\end{itemize}

The remainder of this paper is structured as follows: Section~\ref{sec:Problem} briefly introduces TLS resumption and describes the performance problems of TLS resumption per hostname that we aim to solve.
Section~\ref{sec:Delegation} summarizes the proposed TLS extension.
The evaluation results are presented in Section~\ref{sec:Evaluation}.
Security and privacy considerations of the proposed TLS extension are discussed in Section~\ref{sec:Discussion}, and related work is reviewed in Section~\ref{sec:Related}.
Section~\ref{sec:Conclusion} concludes the paper.

\section{Problem Statement} \label{sec:Problem}
In this section, we review the session resumption mechanism as known from TLS 1.3~\cite{rfc8446}.
Then, we describe the performance problem of TLS resumption per hostname that we aim to solve.

\subsection{TLS resumption}

Transport Layer Security (TLS) is a cryptographic protocol that provides authentication, confidentiality, and data integrity for end-to-end communication.
It finds widespread use in applications such as web browsing, email, and voice over IP (VoIP).
The latest version of it is TLS 1.3~\cite{rfc8446}.
It provides the option to establish an encrypted channel with either a full or a resumed handshake.
Compared to the full handshake, the resumed handshake of TLS~1.3 provides significant performance gains.
The most time-consuming operations in a TLS full handshake are related to the authentication of the server's identity~\cite{bench_wolfssl}.
These operations involve the computation of a signature with the server's private key.
Additionally, they require the client to verify the server's certificate, which includes to check the full certificate chain and to verify the server's signature with the public key contained in the presented certificate.

Resumed handshakes reuse the cryptographic state of a previous connection between two communication partners.
In the resumption handshake, the communication partners authenticate each other by their ability to reuse the cryptographic state of a previous connection.
As a result, resumption handshakes skip the computationally expensive public-key cryptography to authenticate the server's identity.
Besides a lower computational overhead for resumed connections, TLS~1.3 provides also a resumed handshake that requires one round-trip time (RTT) less than the full handshake to establish the encrypted channel.
As a drawback, these resumed TLS~1.3 handshakes impact the client's privacy as the shared secret can be used as a tracking mechanism~\cite{sy2018tracking}.
Furthermore, the resumed 0-RTT handshake does not protect the server's applications against replay attacks, which TLS itself guards against for other handshake modes.
For a comprehensive description of this reduced security guarantees of the 0-RTT resumed handshake and more details on TLS~1.3, we refer readers to RFC~8446~\cite{rfc8446}.

\subsection{The limitation of TLS resumption per SNI}

According to the specification of TLS 1.3~\cite{rfc8446}, a resumption handshake \textit{should} only be used when the hostname of the server, also known as server name indication (SNI), matches the server's hostname of the original TLS session.
Because of this recommendation of TLS~1.3, the use of resumption handshakes is practically restricted to revisits to servers with the same SNI.
This approach provides only performance benefits during the first visit of a website if it is required to establish multiple TLS connections to the same SNI.

However, we find that the web has a complex structure where accessing a web page requires an average of 19 TCP connections to several hosts~\cite{HTTP_Archive}.
Assuming that all of these connections are TLS encrypted, this results in 19 TLS full handshakes for the first visit of an average website.
TLS resumption across hostnames can potentially further reduce this large number of TLS full handshakes to realize performance improvements.

Only with respect to network latency, these TLS full handshakes can cause a significant latency overhead \textit{x} during web page loading compared to the use of resumed 0-RTT handshakes.
Note, that each resumed 0-RTT handshake saves one round-trip time compared to the full handshake.
For the 19 connections of the average website, this reduced latency overhead can sum up to 19 RTTs when all connections are established sequentially.
The lower boundary of the reduced latency overhead is one RTT if all 19 connections are established in parallel.
Equation~\ref{eq:latency_overhead} shows these boundaries of the latency overhead \textit{x}.
\begin{equation}\label{eq:latency_overhead}
RTT \leq x \leq \sum_{i=0}^{19} RTT_{i}
\end{equation}
The average round-trip time for mobile LTE connection in the U.S. is approx. 60\,ms to reach popular online services~\cite{opensignal}.
Thus, for the considered average web page the induced latency overhead by these initial handshakes can reach up to 1.14\,s for LTE connections.
Note, that the round-trip time for 3G and WiFi connections are on average longer than for LTE connections, with a latency of 212~ms and 151~ms respectively~\cite{opensignal2}.
Therefore, these connections types experience an even longer latency overhead for the same web page.

However, the use of resumed handshakes also significantly reduces the latency overhead with respect to the CPU time.
Measurements of the CPU time for TLS 1.2~\cite{cloudflare_CPU} indicate that a resumed handshake requires only 0.3~ms compared to a full handshake with 6.9~ms.
Thus, based on this measurement the computational effort of a full handshake seem to be 23 times higher than for a resumed handshake.
With respect to the latency overhead, each resumed connection saves about 6.6~ms in CPU time on the sampled test setup.
For the average website, this leads to savings in the page loading time between 6.6~ms for parallel connections and 125.4~ms for 19 sequential connections.

In total, the above paragraphs highlight that the latency overhead of loading web pages can be significantly reduced if TLS full handshakes are replaced with resumed handshakes.
However, the restriction of TLS~1.3 to use resumption handshakes only for revisits to the same SNI provides a practical barrier to increase the number of resumed handshakes during the first visit of a website.
For example, a redirect from \textit{https://example.com} to \textit{https://www.example.com} requires two TLS full handshakes because these are two different SNIs.
Similar, if \textit{https://www.example.com} includes resources from \textit{https://static.example.com} the loading of the website requires two independent TLS full handshakes.
This policy of TLS~1.3 is appropriate if it is intended that a TLS resumption handshake between the different SNIs \textit{example.com}, \textit{www.example.com}, and \textit{static.example.com} should not be possible.
For example, if \textit{www.example.com}, and \textit{static.example.com} are operated by different entities that do not trust each other.
However, if  \textit{www.example.com}, and \textit{static.\-example.com} are operated by the same entity or by entities that trust each other, then resumption handshakes between these SNIs should be possible.
Hence, this approach would use resumption handshakes with SNIs, that have not been visited previously.
As a result, the latency overhead from loading a website that includes resources from many SNIs for the first time can be significantly decreased by this approach, when some of these SNIs have a trust relationship between each other.

Note, that the specification of TLS~1.3~\cite{rfc8446} appreciates that performance optimizations are feasible if clients resume to servers with different hostnames.
However, it does not provide an approximation of these performance gains nor does it describe means to implement the exploitation of these performance optimizations.

\section{TLS resumption across hostnames} \label{sec:Delegation}

In this section, we propose a TLS extension that guides the use of TLS resumption across different hostnames, i.e., it allows to inform clients that a TLS connection with SNI $\mathcal{A}$ can also be resumed with SNI $\mathcal{B}$.
This information can be forwarded during the TLS handshake via our proposed TLS extension with the type \textit{resumption\_across\_sni}.

Clients that support the TLS extension can indicate this within their \textit{ClientHello} message.
For this purpose, they include the appropriate extension type with an empty data field to their message.
Servers must only send the \textit{resumption\_across\_sni} extension to clients who signaled their support for it within their \textit{ClientHello}.
In this case, the server sends a list of SNIs that support the resumption based on the TLS state of the original session.
This list of SNIs is sent within the data field of the \textit{resumption\_across\_sni} extension, which in turn is sent as extension data for the servers certificate but is not part of the certificate itself.
Note, that this part of the server's response uses transport encryption to protect against network-based attackers.

Upon receiving the server's response, the client must verify that each SNI provided within the \textit{resumption\_across\_sni} extension is also contained in the server certificate.
The specification of TLS~1.3~\cite{rfc8446} instructs that a client can only resume a session with a new SNI $\mathcal{B}$, if the server certificate presented in the original session with SNI $\mathcal{A}$ is valid for SNI $\mathcal{B}$.
Thus, the client should only use the session resumption mechanism with SNIs that can be authenticated by the private key of the server's TLS certificate.

To establish a connection to one of these SNIs, the client can directly use a resumption handshake for which it utilizes the state of the original session.
To support the proposed TLS extension on the server-side, the involved SNIs are required to share cryptographic state among each other. For TLS~1.3 this depends on the construction approach of the \textit{pre-shared keys} that are used to conduct the resumption of a prior session.
The encrypted TLS connection state either directly contains a \textit{pre-shared key} or the connection state contains a database lookup that refers to the \textit{pre-shared key} in a database instead.
In the direct case, the involved SNIs need to share a secret key that enables them to retrieve the secret server-side connection state from the \textit{pre-shared key} provided by the client.
In the database case, the different SNIs need to share their access to a common database containing their secret server-side connection states.

Note, that the proposed TLS extension can be used in combination with TLS version~1.2 and lower.
Compared to TLS~1.3, these older TLS versions do not apply the concept of encrypted extensions.
Hence, the server's response has to be transmitted in the unencrypted list of extensions within the respective \textit{ServerHello} message.

\section{Evaluation} \label{sec:Evaluation}

In this section, we investigate the real-world impact of our proposed TLS extension.
For that, we first study the delay overhead of different TLS handshakes to substantiate the performance benefits of TLS resumption. Subsequently, we investigate real-world websites and the number of sequential TLS connections required to load them as well as existing trust relationships in between hostnames within the respective domain trees.
Finally, we simulate the performance impact of our proposed TLS extension on the page loading behavior of the investigated websites.

\subsection{Delay overhead of TLS connection establishment}\label{sec:delay_overhead}

 \begin{table*}[tb]
 \caption{Mean duration to establish a TLS connection via different handshake modes between the client-server pair and to conduct a short data transfer.}
  \label{tab:Resumption_comparison}
 \centering
 \begin{tabular}{lrrrrr}
 \toprule
\multicolumn{1}{c}{Network} & \multicolumn{2}{c}{TLS 1.2} & \multicolumn{3}{c}{TLS 1.3} \\
 \cmidrule(lr){2-3}
 \cmidrule(lr){4-6}
\multicolumn{1}{c}{latency} & \multicolumn{1}{c}{Full} & \multicolumn{1}{c}{Resumed} & \multicolumn{1}{c}{Full} & \multicolumn{1}{c}{1-RTT resumed}& \multicolumn{1}{c}{0-RTT resumed} \\
 \midrule
$\approx$0.3 ms& 26.66 ms & 2.69 ms & 29.17 ms  & 6.34 ms & 6.57 ms \\
50 ms& 237.86 ms & 154.20 ms & 190.06 ms  & 160.12 ms& 109.61 ms  \\
100 ms & 439.08 ms & 304.50 ms & 340.81 ms & 310.27 ms& 209.72 ms \\
150 ms& 639.15 ms & 454.621 ms  & 490.87 ms & 460.26 ms & 309.44 ms \\
 \bottomrule
 \end{tabular}
 \end{table*}

In this section, we study the delay overhead and the CPU time of different TLS handshake modes. The delay overhead is the additional time experienced by a user if a full TLS handshake instead of a resumed handshake is used.
The CPU time reflects more an economic and environmental perspective, as a CPU is capable to resume more connections than conducting full TLS handshakes within the same time frame.

\subsubsection{Evaluation setup}\label{sec:eval_setup}

For the experiment, we compare the required time to download a small web page from a single host using standard TCP together with different TLS handshake versions to establish the encrypted channel. The tested TLS handshakes are full TLS~1.2, TLS~1.2 resumption via session identifier, full TLS~1.3, 1-RTT TLS~1.3 resumption, and 0-RTT TLS~1.3 resumption.

We use two virtual machines, one acting as web server and the other one as client.
The virtualization is realized on the same host using  qemu 2.8 and libvirt 3.0.0.
This test setup leads to short network latencies with an average ping of 0.3 milliseconds (ms) between the virtual machines. The host machine was equipped with an Intel Xeon E5-1660 v4 CPU with 32GB of RAM and runs Debian stretch. The client and server virtual machines were both set up with 4~GB of RAM and were running an Ubuntu 18.10, respectively. The server ran the example server program shipped with the wolfSSL library~\cite{wolfssl}.
After successfully establishing a TLS connection, this program responds with a short string to the client's request.
The client ran the corresponding example client program of wolfSSL that establishes a TLS session to the server, issues a request and waits for the server's response before it terminates the TLS session.

For TLS~1.3 we used the forward-secure cipher suite \textit{TLS\_AES\_128\-\_GCM\_SHA256}.
As this particular cipher suite is not available in TLS~1.2, we used the most similar forward-secure cipher suite \textit{ECDHE\_RSA\_AES128\-\_GCM\_SHA256}.
To account for skews in the measurements, we repeated the experiment 1000 times and measured the elapsed wall-clock time.
We conducted our measurements with the client's network interface configured to simulate network latencies of 0.3~ms, 50~ms, 100~ms, and 150~ms with iproute2's \texttt{tc} program.
We recorded and inspected the network traffic of the virtual network interface to validate a correct behavior of our evaluation setup.

\subsubsection{Measuring the elapsed time}\label{sec:elapsed_time}

The delay overhead measurements are summarized in Table~\ref{tab:Resumption_comparison}.
We find that independent of the tested TLS version and network latency the resumed connection establishment saves at least 22.6~ms compared to the full handshakes.
For TLS~1.2 and a latency of approximately 0.3~ms this reduces the overhead of the connection establishment by a factor of almost ten.
The absolute reduction of the delay overhead between the full handshake and resumed connection establishment increases with an increasing network latency, except for the TLS~1.3 1-RTT resumed handshake.
This behavior can be attributed to the saved round-trip times from resumed TLS~1.2 and resumed TLS~1.3 0-RTT handshakes compared to the corresponding full handshake.
We observe, that a TLS~1.2 full handshake requires one RTT delay to establish the transport connection, another two RTTs to establish the encrypted channel, before the last RTT requests and retrieves the small web page.
As expected, the TLS~1.3 full handshake abbreviates this TLS connection establishment by a single RTT.

Considering the number of required round-trips times for each measurement, we find that the duration of the connection establishment is shorter for a network latency of approximately 0.3~ms than for higher network latencies.
For example, the full TLS~1.3 handshake has a delay overhead of one RTT for the TCP connection, one RTT to establish the encrypted channel,  and another RTT to request and retrieve the small web page.
Thus, the delay overhead of the data transfer is about 0.9~ms for a network latency of approximately 0.3~ms and 150~ms for a latency of 50~ms.
Subtracting this delay overhead from the respective results of Table~\ref{tab:Resumption_comparison}, leads to a gap of about 10~ms as shown in Equation~\ref{eq:gap}.
\begin{equation}\label{eq:gap}
190.06~ms-150~ms-29.17~ms-0.9~ms = 9.99~ms
\end{equation}
We assume that this time gap is caused by parallel operations of both peers that occur when the latency in between them is smaller than the time required to compute the necessary cryptographic operations.
Thus, with higher latencies peers will sequentially compute operations during connection establishment, while shorter network latencies induce overlapping times for cryptographic computations at client and server.

We define the reduced delay by using a 1-RTT resumed handshake or a 0-RTT resumed handshake instead of a full TLS~1.3 connection establishment as $\Delta_{1RTT}$ and $\Delta_{0RTT}$, respectively.
Based on our measurements, we find that $\Delta_{1RTT}$ is in an interval between 22.83~ms and 30.61~ms (see Equation~\ref{eq:delta_1rtt}).
\begin{equation}\label{eq:delta_1rtt}
22.83~ms \leq \Delta_{1RTT}  \leq 30.61~ms
\end{equation}
However, for $\Delta_{0RTT}$ such an interval depends on the round-trip time between the client and server, as shown in Equation~\ref{eq:delta_0rtt}.
Thus, for larger network latencies the performance benefit of using a 0-RTT resumed handshake instead of a 1-RTT resumed connection establishment increases.
\begin{equation}\label{eq:delta_0rtt}
22.3~ms + RTT \leq \Delta_{0RTT}  \leq 31.43~ms + RTT
\end{equation}
For an average LTE connection in the U.S. with a network latency of 60~ms~\cite{opensignal}, we thus expect that a TLS~1.3 connection using a 0-RTT handshake instead of a full handshake reduces the delay overhead at least by 82.3~ms.

\subsubsection{Measuring the CPU time}

For this measurement, we deployed the same test setup as described in Section~\ref{sec:eval_setup}. Furthermore, we utilized the same example programs of the wolfSSL library~\cite{wolfssl} to run the server and client. However, we started these programs with the \textit{time} program, which measures the CPU time that was consumed during the execution of another program. Thus, it provides us a metric to assess the conducted computations on the client- and server-side during the corresponding TLS connection establishment.

Table~\ref{tab:CPU_time_comparison} provides the mean values of the CPU time for the different TLS versions based on 10\,000 TLS connection establishments each.
A full TLS handshake consumes between 7.84~ms and 9.22~ms of CPU time per peer.
A resumed TLS~1.2 handshakes requires a CPU time between 0.76~ms and 1.33~ms.
Resumed connection establishments with TLS~1.3 require between 2.33~ms and 2.62~ms of CPU time per peer.
Note, that the measured resumed TLS~1.3 handshakes conduct a Diffie-Hellman key exchange, which establishes a forward-secure communication channel.
This forward-secrecy is not provided by resumed TLS~1.2 handshakes, which leads to a smaller CPU time compared to resumed TLS~1.3 connections.

In total, our results indicate that with respect to the CPU load at least six resumed TLS~1.2 connections can be established instead of a full TLS~1.2 handshake.
For TLS~1.3, around three resumed handshakes can be performed with the same CPU time as a full handshake.
Thus, an increased usage of resumed handshakes on the web allows to significantly reduce the required CPU time of TLS connection establishments. Note, that savings with respect to the CPU time provide various benefits, like a reduced energy consumption of the peers and reduced hardware requirements.

  \begin{table*}[tb]
 \caption{Mean CPU time to establish a TLS connection via different handshake modes between the client-server pair and to conduct a short data transfer.}
  \label{tab:CPU_time_comparison}
 \centering
 \begin{tabular}{lrrrrr}
 \toprule
\multicolumn{1}{c}{Peer} & \multicolumn{2}{c}{TLS 1.2} & \multicolumn{3}{c}{TLS 1.3} \\
 \cmidrule(lr){2-3}
 \cmidrule(lr){4-6}
\multicolumn{1}{c}{} & \multicolumn{1}{c}{Full} & \multicolumn{1}{c}{Resumed} & \multicolumn{1}{c}{Full} & \multicolumn{1}{c}{1-RTT resumed}& \multicolumn{1}{c}{0-RTT resumed} \\
 \midrule
Server& 8.02 ms & 1.33 ms & 7.84 ms  & 2.33 ms & 2.62 ms \\
Client& 8.26 ms & 0.76 ms & 9.22 ms  & 2.38 ms & 2.46 ms  \\
 \bottomrule
 \end{tabular}
 \end{table*}

\subsection{Investigating the loading behavior of the Alexa Top~1K Sites}\label{sec:loading_behavior}

Performance improvements of the proposed TLS extension over standard TLS resumption are possible if a visited hostname shares its TLS state with another hostname that the client will connect to later on.
Hence, TLS resumption across hostnames can provide performance improvements within the visit of a single website and in between visits of different websites.
In the following, we will investigate the benefits of our proposal with respect to a single visit of a website.
For this purpose, we derived domain trees for the Alexa Top~1K Sites~\cite{Alexa}.
These domain trees indicate the causal relations between the hostnames requested during loading the respective page.
Figure~\ref{fig:Domain_tree} shows such a domain tree for the root-domain \textit{google.com}.

\begin{figure}[tbp]
\centering
\includegraphics[width=0.47 \textwidth]{./Pic/Plot_domains_tree_v2}
\caption{Domain tree of root-domain google.com, which holds the first rank within the Alexa Top1K Sites.}
\label{fig:Domain_tree}
\end{figure}

To generate domain trees, we analyzed results of the online service \textit{urlscan.io}.
It scans websites with the Google Chrome browser in headless mode and provides an overview of the browser's requests during the page loading.
Furthermore, this service also reports the origin of a new request that allows us to derive the causal sequence of those requests.
We conducted our scans of the Alexa Top~1K Sites on the 8th of November 2018.
We successfully retrieved the domain trees for 839 websites and experienced errors for the remaining 161 domain trees, which manifests an error rate of 16.1\%.
Errors occurred for various reasons on protocols like IP, DNS, SPDY, and TLS.
For example, due to timeouts, unreachable IP addresses, a failed domain name resolution, and protocol errors.
In the following, we assume that the successfully collected website data is qualified to represent the average loading behavior of the Alexa Top~1K Sites.

Based on the collected data, we find the 839 websites required connections to 17\,525 different hostnames to be loaded.
About 97\% of these different hostnames supported TLS encryption.
As our evaluation focuses on the performance improvements for TLS connections, we excluded the remaining 541 hostnames without support for TLS from our evaluation.
On average, we observe that each website within the Alexa Top~1K Sites requires TLS connections to 20.24 different hostnames for its retrieval.
Figure~\ref{fig:required_handshakes} shows the distribution of the required number of TLS connections to different hostnames for the websites in our data set.
We find, that 95.2\% of the investigated websites require more than a single TLS connection for its retrieval. Furthermore, we note that 73.3\% of the analyzed websites require less than 26 full TLS handshake to load the site.
We find that 11.9\% of all observed websites require eight full TLS handshakes, which is the most common configuration.
Note that also \textit{google.com} utilizes this configuration as shown in Figure~\ref{fig:Domain_tree}.

\begin{figure}[tbp]
\centering
\includegraphics[width=0.47 \textwidth]{./Pic/required_handshakes}
\caption{Share of Alexa Top~1K Sites over the number of required full TLS handshakes to retrieve the website. Note, that this plot is cut off at 25 full handshakes.}
\label{fig:required_handshakes}
\end{figure}

Using the generated domain trees, we determine the shortest path between the root-domain and all other hostnames within the domain tree.
The longest determined path indicates the maximum number of sequentially established TLS connections required to load the page.
For example, the domain tree of \textit{google.com} requires four sequential TLS connection to load the website (see Figure~\ref{fig:Domain_tree}).
This longest path traverses the hostnames \textit{google.com},  \textit{www.google.com},  \textit{www.gstatic.com}, and  \textit{apis.google.com}.
We use the longest path of sequential TLS connections as metric to describe the impact of TLS connection establishment on the website loading performance.
We assume that a website requires all its TLS connections to be established before the loading of the site can be completed.
For the loading of \textit{google.com}, this leads to four times the delay overhead of a TLS full handshakes until all required TLS connection can be established.

\begin{figure}[tbp]
\centering
\includegraphics[width=0.47 \textwidth]{./Pic/longest_fullhandshake_path}
\caption{Share of Alexa Top~1K Sites is plotted over the number of required sequential TLS connections to load the respective website.}
\label{fig:longest_fullhandshake_path}
\end{figure}

Figure~\ref{fig:longest_fullhandshake_path} presents a distribution of the investigated websites over the number of sequential TLS connections required loading the site.
As expected from Figure~\ref{fig:required_handshakes}, we find that 4.8\% of the investigated websites require only one sequential TLS connection to retrieve the site.
63.0\% of the websites within the Alexa Top~1K Sites require less than five sequential TLS connections to load them, while no website requires more than eight sequential TLS connections.

\subsection{Measuring trust-relations within the domain trees of the Alexa Top~1K Sites} \label{sec:trust_relations}

To successfully conduct TLS resumption across hostnames, we require the involved hosts to share their secret TLS state. Within this evaluation, we define the sharing of secret TLS state between different hostnames as a trust-relation. We use two approaches to assess trust relations between different hostnames.
First, we assume a trust-relation exists, if a private key of a TLS certificate is valid to authenticate both hostnames.
Second, if a TLS session can be successfully resumed across two hostnames, then we also assume a trust-relation between two hostnames.

To identify trust relations between hostnames based on TLS certificates, we analyze our data collection described in Section~\ref{sec:loading_behavior}.
The results of the Alexa Top~1K Sites include the \textit{Subject Alternative Names (SAN)} stated in the respective TLS certificate.
This SAN-list indicates the hostnames that can be authenticated via the presented certificate and thus can be used to infer trust relations.

We analyzed the SAN-lists of the 16\,984 hostnames supporting TLS that we identified during the scan of the Alexa Top~1K Sites.
For each domain tree, we grouped all hostnames that have a trust-relation with each other.
In total, we find that on average an Alexa Top1K Site connects to 20.24 different hostnames, which form 9.49 trust groups on average.
The mean size of a trust groups is 2.13 as shown in Table~\ref{tab:trust-groups}.
This result indicates that trust relations between nodes of domain trees are a common phenomenon on the web.
However, these determined trust relations do not assure that TLS resumption across different hostnames are feasible.

 \begin{table}[htbp]
   \caption{Mean size of TLS trust groups within the domain trees of each Alexa Top~1K Site}\label{tab:trust-groups}
 \centering
 \begin{tabular}{ccc}
 \toprule
 \makecell{Results based upon\\TLS certificates} & \makecell{Results based upon\\TLS resumption}& \makecell{Union of both\\evaluations}\\
 \midrule
 2.13 & 1.50 & 2.42 \\
 \bottomrule
 \end{tabular}
 \end{table}

To further substantiate the feasibility of our proposal, we attempted to resume TLS sessions between all nodes of each domain tree.
We conducted this measurement on the 25th of January 2019 using the OpenSSL library version~1.1.0f~\cite{openssl} to establish a TLS connection to each node of a respective domain tree.
For this measurement, we used the resumption mechanisms session ID's and session tickets to resume a connection via TLS versions 1.0, 1.1, and 1.2.
We observed that with an exception of 54 hostnames all other hostnames preferred connections via TLS~1.2. Furthermore, our results indicate session tickets are the preferred resumption mechanism for 81.2\% of the hostnames.

For this experiment, we assume that websites supporting the latest TLS version 1.3 will also support one of the earlier TLS versions.
Subsequently, we attempted to resume each initial connection to the domain at each of the other hostnames within the domain trees.
This approach provided us with a list of trust relations for each node of a domain tree.
We evaluated these lists similar to the SAN-lists to determine trust relations within each domain tree of the Alexa Top~1K Sites.

Based upon this measurement, we find that each Alexa Top~1K Site has on average 13.51 trust groups.
As shown in Table~\ref{tab:trust-groups}, the mean size of these trust groups is 1.50.
We observe, that the size of trust groups differ between our conducted investigations.
This indicates that some trust relations identified via TLS certificates do not enable the resumption of TLS session across the corresponding hostnames.
Subsequently, we study these both sets of trust-relation by computing their union.
We notice that also a significant share of trust relations determined via successful TLS resumptions is uncovered by the trust relations identified via TLS certificates.
Considering the trust relations of both sets, we find a mean size of the trust groups per Alexa Top~1K Site of 2.42.

\begin{figure}[tbp]
\centering
\includegraphics[width=0.47 \textwidth]{./Pic/root_trustgroup_size}
\caption{Share of Alexa Top~1K Sites is plotted over the size of the trust group that includes the root-domain. Note, that this plot is cut off at a trust group size of 25.}
\label{fig:root_trustgroup_size}
\end{figure}

Figure~\ref{fig:root_trustgroup_size} provides additional insights into the distribution of the group size.
It plots the share of Alexa Top~1K Sites in dependence of the size of trust groups including the root-domain.
We find, that 77.12\% of the root-domains have a trust-relation to another hostname within their domain tree.
Furthermore, 90.94\% of the root-domains have a trust-relation to less than eleven hostnames within their domain tree.
Popular configurations have one or two trust relations for the root-domain, which represent 19.66\% and 17.04\% of the Alexa Top~1K Sites respectively.
Furthermore, we observe that 40 websites within the Alexa Top~1K Sites are served via their root-domain and do not require an additional TLS connection to a subdomain for their retrieval.

\subsection{Simulating TLS resumption across hostnames}

In this section, we study the real-world impact of TLS resumption across hostnames.
For this purpose, we conduct a simulation based on the loading behavior of the Alexa Top~1K Sites (see Section~\ref{sec:loading_behavior}) and the measured trust relations within their domain trees (see Section~\ref{sec:trust_relations}).
We start by investigating the performance impact of our proposal when loading a single website.
Subsequently, we extend this scenario by analyzing the visits to different websites.

\subsubsection{Visiting a single website}\label{sec:single_website}

Our proposal is capable to significantly accelerate the first visit of an average website.
To substantiate this claim, we provide simulation results for the Alexa Top~1K Sites in this section.

Our simulation assumes the domain trees and trust groups as described in Section~\ref{sec:loading_behavior} and~\ref{sec:trust_relations}.
Furthermore, we assume that a full TLS handshake to any member of a trust group enables us to subsequently establish resumed connections to all other hostnames within the same trust group. In the real world that might not be always the case, as multiple TLS connections might be established in parallel, resulting in more full handshakes.

Using the proposed TLS extension, we can reduce the number of required full handshakes to download a website by 58.75\% on average.
Absolute numbers are provided in Table~\ref{tab:fullhandshake_cross_host} and indicate that our approach converts on average 11.89 full to resumed handshakes.
Furthermore, Table~\ref{tab:fullhandshake_cross_host} indicates that the traditional TLS resumption mechanism cannot reduce the number of full handshakes to different hostnames.
However, the traditional TLS resumption is still beneficial when multiple TLS connections to the same hostname are required for loading the website.

Assuming that each resumed TLS connection saves approximately 6~ms of CPU time of each peer (see Table~\ref{tab:CPU_time_comparison}), then our proposal reduces the required CPU time to load a website on average by 71.34~ms.
Assuming a full handshake to require 8~ms of CPU time per peer, then our proposal saves 44.06\% of the CPU time to load an average website initially.

 \begin{table}[htbp]
   \caption{Mean number of required full TLS handshakes to different hostnames to download a website of the Alexa Top~1K list for the first time. Note, that within this simulation trust relations between hostnames are assumed based on the union of presented TLS certificates and practical TLS resumptions.}\label{tab:fullhandshake_cross_host}
 \centering
 \begin{tabular}{ccc}
 \toprule
\makecell{Without TLS\\resumption} & \makecell{With TLS\\resumption}& \makecell{With TLS resumption\\across hostnames}\\
 \midrule
20.24 & 20.24 & 8.35 \\
 \bottomrule
 \end{tabular}
 \end{table}

 Figure~\ref{fig:trustgroup_number} shows the share of Alexa Top~1K Sites in dependence on the number of required full TLS handshakes to retrieve the website.
The results of our simulation are shown as blue circles and the default website loading behavior is marked with green squares (see Figure~\ref{fig:required_handshakes}).
We find that the share of websites that require less full handshakes significantly increased when TLS resumption across hostnames is used.
For example, the share of Alexa Top~1K Sites requiring only one full TLS handshake is 12.87\% when using TLS resumption across hostnames and 4.76\% without considering our proposal.
In total, the share of Alexa Top~1K Sites that require less than five full handshakes is now 42.07\% compared to 14.09\% without our TLS extension.
Furthermore, 95.95\% of the Alexa Top~1K Sites require less than 26 full TLS handshakes following our approach compared to 73.3\% of these websites without enabling TLS resumption across hostnames.

\begin{figure}[tbp]
\centering
\includegraphics[width=0.47 \textwidth]{./Pic/trustgroup_number-diff}
\caption{This plot shows the share of Alexa Top~1K Sites over the number of required full TLS handshakes to retrieve the website. The blue circles mark the values considering TLS resumption across hostnames, while the green squares plot the current default (see Figure~\ref{fig:required_handshakes}). Note, that this plot is cut off at 25 full handshakes.}
\label{fig:trustgroup_number}
\end{figure}

In the following, we investigate the number of required sequential TLS full handshakes to retrieve an average Alexa Top~1K Site.
As shown in Table~\ref{tab:full-handshake-request-path}, the longest path of full TLS handshakes within the domain tree of an average Alexa Top~1K Site is 4.04, independently of the support for traditional TLS resumption.
Our proposal significantly reduced the number of TLS full handshakes required to retrieve an average website.
The longest path of full TLS handshakes decreased to 2.46. Thus, to establish all TLS connections required to retrieve a website on average requires only 2.46 full TLS handshakes and 1.58 resumed handshake instead of 4.04 full handshakes.
Equation~\ref{eq:delta_connect} allows the computation of $\Delta_{connect}$, which we define as the reduced delay until all TLS connections of an average website are established using TLS resumption across hostnames instead of the current default website loading.
\begin{equation}\label{eq:delta_connect}
\Delta_{connect} =
  \begin{cases}
    1.58 * \Delta_{1RTT}       & \quad \text{ for 1-RTT resumptions}\\
   1.58 * \Delta_{0RTT}  & \quad \text{ for 0-RTT resumptions}
  \end{cases}
\end{equation}

With respect to relative numbers, we achieve the most significant improvement for short network latencies.
To establish all connections for an average website via full TLS~1.3 handshakes requires $4.04*29.17~ms=117.85~ms$ for a network latency of approximately 0.3 ms.
TLS resumption across hostnames allows to save $1.58*22.83~ms=36.07~ms$ in this scenario, leading to a performance gain of 30.6\% until all connections are established.

 \begin{table}[htbp]
   \caption{Mean length of the longest path of required full TLS handshakes to different hostnames to retrieve an average website of the Alexa Top~1K list for the first time. }\label{tab:full-handshake-request-path}
 \centering
 \begin{tabular}{ccc}
 \toprule
\makecell{Without TLS\\resumption} & \makecell{With TLS\\resumption}& \makecell{With TLS resumption\\across hostnames}\\
 \midrule
4.04 & 4.04 & 2.46 \\
 \bottomrule
 \end{tabular}
 \end{table}

Figure~\ref{fig:longest_fullhandshake_cross_host_path} provides additional insights on the number of required sequential TLS full handshakes to retrieve an average Alexa Top~1K Site.
Comparing our simulation results plotted as blue circles to the default website loading behavior represented as green squares (see Figure~\ref{fig:longest_fullhandshake_path}), we find that TLS resumption across hostnames significantly reduces the number of sequential TLS full handshakes.
For example, the number of Alexa Top~1K Sites require less than three sequential TLS full handshakes for their retrieval has approximately quadrupled by using TLS resumption across hostnames.
Furthermore, the share of Alexa Top~1K Sites that require more than five sequential full TLS handshakes decreased from 36.95\% to 2.26\%.

\begin{figure}[tbp]
\centering
\includegraphics[width=0.47 \textwidth]{./Pic/longest_fullhandshake_cross_host_path_diff}
\caption{This plot shows the share of Alexa Top~1K Sites over the number of required sequential TLS connections to load the respective website. The blue circles represent the values considering TLS resumption across hostnames, while the green squares plot the current default (see Figure~\ref{fig:longest_fullhandshake_path}).}
\label{fig:longest_fullhandshake_cross_host_path}
\end{figure}

\subsubsection{Visiting different websites}

TLS resumptions are not just feasible within the context of a single website.
For example, if different websites require connections to the same hostname, then a sequential visit to these websites makes TLS resumptions feasible.
In this section, we deploy the same assumptions as in Section~\ref{sec:single_website} to study visits to different websites.
However, we consider only trust relations from the TLS certificates for the simulation as an experimental resumption test between all 16\,984 hostnames present in the Alexa Top~1K sites would result in almost 290~million connection attempts to a rather small group of servers.

In our test scenario, we measure the average of the required number of full handshakes to different hostnames, when visiting different websites within the Alexa Top list.
Table~\ref{tab:fullhandshake_cross_host_two_sites} summarizes these results for the Alexa Top~100 and the Alexa Top~1K Sites.
We find, that the traditional TLS resumption converts about 2.5\% of the full handshakes to resumed connection establishments in the Alexa Top~100 test scenario.
In the same scenario, our proposed approach converts 64.2\% of the full handshakes to resumed connection.
In the larger Alexa Top~1K simulation, we find that traditional TLS resumption allows to reduce the number of full TLS handshakes by 4.1\%, while our approach reduces this number by 55.5\% less full TLS handshakes at the same time.
These results substantiate, that TLS resumption across hostnames significantly improves performance for the encrypted web.

 \begin{table*}[htbp]
   \caption{Mean number of required full TLS handshakes to different hostnames to download two websites of a given Alexa Top list. Note, that within this simulation trust relations between hostnames are assumed based on the presented TLS certificates.}\label{tab:fullhandshake_cross_host_two_sites}
 \centering
 \begin{tabular}{lccc}
 \toprule
\multicolumn{1}{c}{Alexa Top list} & \makecell{Without TLS resumption} & \makecell{With TLS resumption}& \makecell{With TLS resumption\\across hostnames}\\
 \midrule
\makecell{Alexa Top 100}& 25.98 & 25.34 & 9.30 \\
\makecell{Alexa Top~1K}& 41.78 & 40.04 & 18.58 \\
 \bottomrule
 \end{tabular}
 \end{table*}

\paragraph{Summary}
In summary, our results indicate that resumed handshakes have a significantly reduced delay and computational overhead compared to full TLS handshakes.
Moreover, we find that the loading of an average website requires more than 20 TLS connections to separate hostnames, which tend to have a trust relation with each other.
To reduce the overhead caused by the TLS connection establishment, TLS resumption across hostnames provides an efficient mechanisms.
Thus, the average website can be retrieved with 44.06\% less CPU time consumed.
Furthermore, the establishment of the required connections to retrieve the website can be accelerate with up to 30.6\% based on our TLS~1.3 test measurements.

\section{Discussion}\label{sec:Discussion}

In this section, we discuss the security and privacy impact of the proposed TLS extension.
Subsequently, we review developments on the Internet that may affect the impact and benefit of our proposal.

\subsection{Security considerations}

The authentication of the server's identity is a critical part of the TLS handshake.
In the full TLS handshake, the client validates the server's identity based on public-key cryptography.
Thus, the server is required to present a valid certificate containing a public key that confirms the claimed identity.
Furthermore, the client validates that the server can generate a fresh signature with the private key corresponding to the presented certificate/public key.

Within a resumed TLS handshake, these computationally expensive public-key operations are omitted.
The server is authenticated by its knowledge of a cryptographic secret related to the original TLS session, which allows the server to decrypt parts of the resumption handshake.
This practice presents an indirect authentication of the server's identity because the client does not validate the server's certificate and the server's possession of the corresponding private key within the resumed TLS session.
Thus, resumption handshakes require the client to trust the correctness of the server authentication during the original session.

In the scenario of TLS resumption across hostnames, the risk arises that an attacker exploits this weaker validation of the server's identity during the resumption handshake for impersonification attacks.
For example, the client connects with a full TLS handshake to a legitimate but malicious SNI.
The corresponding malicious server then advertises session resumption to an illegitimate SNI that would not withstand a validation of its identity by the client during a full TLS handshake. By using a resumption handshake to connect to this illegitimate SNI, the client may successfully establish a TLS connection without noticing the insufficient authentication of the server's identity.

To avoid such attacks, resumption handshakes need to be restricted to SNI values that are valid with respect to the server certificate presented in the original session.
Note, that this restriction is already a requirement in the specification of TLS~1.3~\cite{rfc8446}.

\subsection{Privacy considerations}

Session resumption mechanisms in TLS~1.3 allow tracking a user across several visits to the same hostname~\cite{sy2018tracking}.
TLS~1.3 uses unique pre-shared key (PSK) identities for session resumption that can be linked to a specific user.
Thus, every time a user presents a cached PSK identity during a connection attempt, this new connection can be linked to the original connection where that unique PSK was issued by the server to the client.
By enabling session resumption across several hostnames, the operators of these hostnames can link user visits to any of these hostnames.
For that, the operators of the contacted hostnames need to share logs with each other.
These logs contain an entry on the freshly issued PSKs to a user, details on the user activities, and if applicable information on the presented PSK by the client during the resumption handshake.
Thus, by using the currently available session resumption mechanisms of TLS and when extending this across hostnames the problem of illegitimate user tracking across hostnames is facilitated.

User tracking across hostnames is a long established privacy problem on the Internet~\cite{bujlow2017survey}.
Assuming that two different websites want to track a specific user, e.g., via HTTP cookies or via TLS session resumption mechanisms, they can use a simple web link with a unique URL. If the user follows that link, then the operators of the hostnames associate the user in their logs with the observed web link.
By sharing their logs and matching the included web links the operators can extract the user behavior across the respective hostnames.
This example indicates that simple web links are sufficient to enable user tracking across hostnames and our proposed approach does not introduce completely new privacy problems for the user.

The average performance of TLS connection establishments depends on the ratio of resumed handshakes per full handshakes.
The higher this ratio is, the lower is the overhead of the TLS connection establishment.
The lifetime of the TLS session resumption mechanisms impacts this performance for a given browsing session, because a shorter lifetime leads to less resumed handshakes per full handshakes.
Furthermore, this lifetime presents an upper bound for the feasible tracking period by the session resumption mechanism~\cite{sy2018tracking}.
By using resumption handshakes across hostnames, we yield the same ratio of resumed handshakes per full handshakes within a shorter lifetime of the session resumption mechanism.
For example, we consider a website that requires TLS connections to two hostnames that support session resumption between each other. By using our approach, we can directly retrieve the website with a full and a resumed TLS connection leading to a ratio of one.
Without the usage of resumption handshakes across hostnames, it requires two retrievals of the same website to yield the same ratio of a resumed handshake per full handshake.
Thus, our approach allows setting the lifetime of the session resumption mechanism to a single website visit to achieve the same performance as the two website retrievals following the current practice of session resumption.
A short lifetime of the resumption mechanism restricts the feasible tracking periods and therefore our approach can lead to improvements for the user's privacy without impacting the performance of the TLS connection establishment.

\subsection{Chances and limitations}

In this section, we review the growing TLS adoption on the web as this development positively contributes to the real-world impact of our proposed TLS extension.
Subsequently, we investigate the adoption of TLS~1.3 0-RTT resumption handshake by popular websites.
This handshake mode does not inherently protect against replay attacks, which restricts its use cases compared to 1-RTT resumption handshake.
If the 0-RTT handshake mode exhibits a lower adoption compared to the 1-RTT resumption mode, then this practice limits the feasible performance optimizations of TLS~1.3 resumption handshakes across hostnames.

\subsubsection{Growing TLS adoption on the web}

The adoption of TLS has significantly increased during the last years~\cite{felt2017measuring}.
To substantiate this statement, Figure~\ref{fig:growing_adoption} shows of the share of encrypted HTTPS requests over a three years' time series.
 This data is collected by regularly retrieving websites using desktop (dashed line) and mobile (dotted line) browsing environments.
 For further details on the methodology of these web scans, we refer the reader to~\cite{HTTP_Archive}.

\begin{figure}[t]
\centering
\includegraphics[width=0.47 \textwidth]{./Pic/Plot_http_archive_TLS_adoption}
\caption{Percent of all requests indicating TLS support is plotted over a time series from January 2016 to December 2018.}
\label{fig:growing_adoption}
\end{figure}

As shown in Figure~\ref{fig:growing_adoption}, the share of HTTPS request on the web increased by more than 50\% during the plotted period.
Research work~\cite{felt2017measuring} expects even further growth of the TLS deployment on the web.
Prior research\cite{sy2018tracking} on TLS session resumption indicates that about 96\% of the websites supporting TLS do also support a session resumption mechanism.
Thus, we expect that the increased deployment of TLS on the web will raise the absolute number of hostnames that support session resumption.

\subsubsection{Measuring the adoption of TLS~1.3 handshake modes}

Besides the full handshake mode, TLS~1.3 provides the option to support 1-RTT and 0-RTT resumption handshakes.
We collected data on the Alexa Top Million Sites~\cite{Alexa} to investigate the adopation of the different TLS~1.3 handshake modes.
We scanned these websites on January 25, 2019 using the library boringssl~\cite{BoringSSL}.
For that, we first established a TLS~1.3 connection via a full TLS handshake. If this connection establishment succeeded, then we directly tried to establish connections via 1-RTT and 0-RTT resumption handshakes.

Table~\ref{tab:alexa_lists} summarizes our findings. 80\,799 websites within the Alexa Top Million list support the TLS~1.3 full handshake. 87.6\% of these websites also support session resumption via 1-RTT handshakes. However, within the Alexa Top 100K this share reaches 96.9\%. Thus, our results indicate widespread support for session resumption by websites supporting TLS~1.3.
Furthermore, our results indicate that 491 websites among the Alexa Top Million list support the 0-RTT handshake mode.
This represents a share of 0.6\% of the respective websites within the Alexa Top Million list that support TLS~1.3.
However, within the Alexa Top~1K this share raises to 7.1\% with nine websites out of 127 websites supporting TLS~1.3.
Overall, the support of 0-RTT handshakes is within our sample lists, at least one magnitude lower compared to the support of 1-RTT resumption handshakes.

 \begin{table}[t]
   \caption{Websites with TLS~1.3-support in Alexa Top lists. Additionally the support of the 1-RTT and 0-RTT session resumption (SR) handshake is indicated.}
  \label{tab:alexa_lists}
 \centering
 \begin{tabular}{lrrr}
 \toprule
\multicolumn{1}{c}{Alexa Top lists} & \multicolumn{3}{c}{\makecell{Share of websites supporting TLS~1.3}} \\
 \cmidrule(lr){2-4}
& \multicolumn{1}{c}{Full mode} & \multicolumn{1}{c}{1-RTT SR}& \multicolumn{1}{c}{0-RTT SR}\\
 \midrule
Alexa Top 10&     10.0\%&10.0\%&0.00\%\\
 Alexa Top 100&  9.0\%&8.0\%&0.00\%\\
 Alexa Top~1K&    12.7\%&11.6\%&0.90\%\\
 Alexa Top 10K&  13.1\%&12.6\%&0.44\%\\
 Alexa Top 100K& 9.2\%&8.9\%&0.19\%\\
 Alexa Top 1M &    8.1\%&7.1\%&0.05\%\\
 \bottomrule
 \end{tabular}
 \end{table}

In total, we find our measurement investigates an early stage of the deployment of TLS~1.3 on the web.
At the time of our scan, still many server vendors and CDNs did not support TLS~1.3~\cite{istlsfastyet}.
Furthermore, some server vendors and CDNs do support TLS~1.3 except for TLS~1.3 0-RTT resumption handshakes~\cite{istlsfastyet}.
We expect that the number of websites supporting TLS~1.3 and their resumption handshakes will raise during the next years as more server vendors and CDNs will support this new TLS version by default.
We assume that the lower deployment of TLS~1.3 0-RTT resumption handshakes is also caused by the lower security guarantees compared to the 1-RTT resumption case.
Thus, we expect this handshake mode will remain less widely adopted compared to the 1-RTT handshake mode.

\section{Related Work}\label{sec:Related}

To the best of our knowledge, we are the first to investigate the performance benefit of TLS resumption across hostnames.
However, prior work~\cite{sy2018tracking, Springall:2016:MSH:2987443.2987480} did already report the sharing of TLS state across hostnames, which is a pre-requisite for resuming a TLS session with another hostname.

Furthermore, also RFC~8446~\cite{rfc8446} briefly discusses the opportunity of performance enhancements based on TLS resumption across hostnames.
This RFC concludes that TLS resumption across hostnames is possible within certain security limitations that lead to a high failure rate for resumption attempts.
However, this RFC did not consider the option of a TLS extension to inform the client about other hostnames that are capable to resume the respective session.
We argue that our proposed TLS extension minimizes this failure rate, as the client will only attempt a resumption handshake with hostnames directly recommended by the server during the original TLS session.

\section{Conclusions}\label{sec:Conclusion}

A TLS extension supporting clients to conduct TLS resumption across hostnames is overdue.
Our evaluations indicate, that the proposed TLS extension yields great performance optimizations for clients and servers on the existing web without affecting the user's privacy and communication security.

\bibliographystyle{ACM-Reference-Format}


\subsection*{Abstract}
We exploit the nondeterminism of LR parsing tables to reason about grammar
ambiguity after a conflict-driven strategy.
First, from parsing tables we define specialized structures, called SR-automata.
Next, we search for ambiguous words along the paths of SR-automata that reach a conflict
state and then diverge along the branches corresponding to distinct resolutions
of the conflict.

\

\noindent
{\fontsize{9.5}{12.5}\sffamily\bfseries {1998 ACM Subject Classification}}
{\fontsize{9.5}{12.5}\sffamily {F.4.2 Grammars and Other Rewriting Systems}}

\

\noindent
{\fontsize{9.5}{12.5}\sffamily\bfseries {Keywords}}
{\fontsize{9.5}{12.5}\sffamily {Context-free grammars; LR parsing; Ambiguity}}

\section{Introduction}

Grammar ambiguity is undecidable~\cite{Cantor62,Floyd62}, and
various, inevitably incomplete, approaches
have been investigated to detect ambiguity in some cases
(e.g., \cite{Gorn63,Amber01,Schmitz07,AxelssonHL08,BrabrandGM10,Schmitz10,Basten11}).
Some of these techniques are exploratory, meaning that ambiguous derivations
are searched for among those generated by the grammar.
Other methods are approximate, in the sense that the decision is taken
on some approximation of the given language.

Here we present a strategy for ambiguity detection that is centered around
a conflict-driven post-processing of the output of
a bottom-up parser.
We base our analysis on the widespread availability of LALR(1)~\cite{DeRemer69}
parser generators
(e.g.~\cite{YaccManual74,BisonManual}).
If the parsing table for a given grammar is deterministic, then
the grammar is surely unambiguous.
On the other hand, if the parsing table is nondeterministic,
then the grammar might be ambiguous, or it might belong
to a deterministic class bigger
than that for which the table was built.
Hence, we can let a parser generator do a pre-screening of unambiguity, and
perform further checks only on those grammars that lead to the construction
of nondeterministic tables.
Above we made the case for LALR(1) parsing tables.
The technique, however, applies to all the tables constructed as controllers
for the shift-reduce algorithm
(e.g., SLR(1)~\cite{DeRemer71}, LR(1)~\cite{AhoU77}).
So, in what follows, we generically refer to tables for LR parsing in its
broadest sense~\cite{Knuth65}, and indeed,
the bigger the class analyzable by the table,
the higher the probability that its nondeterminism depends on ambiguity.

To detect ambiguity, we focus on the conflicts found in nondeterministic tables.
First, we define \SRauta.
They are built from the characteristic automata underlying parsing tables,
and encode all the information needed to mimic the shift-reduce algorithm.
There is a main difference, though, between the two sorts of automata.
In the case of \SRauta, the accepted words are
obtained by a specialized concatenation of the terminals found along
an unbroken path from the initial to the final state.
This does not apply to characteristic automata, where, due to reductions,
the same words are recognized by concatenating the terminals scattered along
segmented paths.

Working on \SRauta, we look for ambiguous words among those that can be
recognized along paths that traverse a conflict state.
This activity is partially abstracted by operating on approximated versions
of \SRauta\ that are forgetful of the details needed to control executions,
and hence accept a superset of the language under investigation.
Essentially, we guess the ambiguous words by searching paths on the approximated
structure.
We then go back to the \SRauton\ to validate those words against
proper executions of the shift-reduce algorithm.

The rest of the paper is organized as follows.
Sec.~\ref{sec:preliminaries} presents basic definitions and conventions.
\SRauta\ and their properties are dealt with in Sec.~\ref{sec:srautomata}.
The proposed detection strategy is the subject of Sec.~\ref{sec:detection},
and Sec.~\ref{sec:conclusions} concludes the paper.
We assume the reader be familiar with the theory of LR parsing
(see, e.g.,~\cite{AhoLSU06,SippuS90}).

\section{Preliminaries}
\label{sec:preliminaries}

In this section, we will collect basic definitions and the adopted conventions.

A context-free grammar is a tuple $\mathcal{G} = (V,T,S,\mathcal{P})$ where
$V$ is the finite set of terminals and nonterminals,
$T$ is the set of terminals,
$S\in (V\setminus{T})$ is the start symbol, and
$\mathcal{P}$ is the finite set of productions.
We assume grammars be reduced, and adopt the following notational conventions.
The empty string is denoted by $\epsilon$,
$V^*$ is ranged over by $\alpha,\beta,\ldots$,
$(V \setminus T)$ by $A,B,\ldots$,
$T$ by $a,b,\ldots$,
$T\cup\set{\$}$ by $x,x',\ldots$, and
$T^*$ by $w,w',\ldots$.
Productions are written
$A\rightarrow\beta$, and
$\length{\beta}$ denotes the length of $\beta$.
Moreover, $\Flang{\mathcal{G}}$ stands for the language generated by
$\mathcal{G}$.

Given any context-free grammar $\mathcal{G}$,
LR parsing is applied to strings followed by the endmarker symbol $\$\notin V$.
The parsing table is constructed for the augmented version of $\mathcal{G}$
defined as
$(V',T',S',\mathcal{P}')$ where
$S'$ is a fresh symbol,
$V' = V\cup\set{S'}$,
$T' = T\cup\set{\$}$,
and $\mathcal{P}' = \mathcal{P}\cup\set{S'\rightarrow{S}\$}$.
Parsing is performed by running the shift-reduce algorithm~\cite{Knuth65}
using a parsing table as controller, and reading the next input symbol.
Two auxiliary structures are involved: a stack to trace the history of
computation by recording the traversed states, and a stack to keep trace
of the reductions performed.
When the parsing of a given word $w$ is successful, the second stack, named
\Ftree{w}, contains, from top to bottom, the sequence of productions for the
rightmost derivation of $w$ in $\mathcal{G}$.

Different controllers are adopted for different classes of LR parsing.
Nonetheless, in any case the parsing table is mechanically computed from two
objects that are finer or coarser depending on which class of grammars
the table is supposed to parse~\cite{bobu}.
These objects are
a \emph{characteristic automaton}, and
a \emph{lookahead function}.
Characteristic automata are deterministic finite state automata.
Their states are sets of items, i.e. of productions with a dot at some position
of their right-hand side.
The initial state is the one containing the item $S'\rightarrow\dotInItem{S}\$$,
and the final state is the one containing $S'\rightarrow{S}\$\dotInItem$.
The transition function of the characteristic automaton is used to set up
the \emph{shift} and the \emph{goto} entries of the parsing table.
A directive to \emph{reduce} the production $A\rightarrow{\beta}$
is inserted in the table at the entry $\pair{P}{x}$ iff
the state $P$ of the automaton contains the item $A\rightarrow{\beta}\dotInItem$
and $x\in\Fla\pair{A\rightarrow\beta}{P}$, where
$\Fla\pair{\_}{\_}$ is the lookahead function mentioned above.

Parsing tables can be nondeterministic, meaning that they may have multiply-defined
entries containing either a shift and a reduce directive (called s/r conflict) or
multiple reduce directives relative to distinct productions (called r/r conflict).
Here we are mainly interested in nondeterministic parsing tables.
To run the shift-reduce algorithm over them, we assume that,
any time control goes to an entry of the table that contains a conflict, a random local
choice resolves the conflict in favour of one of the possible alternatives.

In what follows,
given a characteristic automaton ${\mathcal{A}}$ for the augmented version
of a grammar $\mathcal{G}$
and an associated lookahead function $\Fla$,
we will refer to the pair $\pair{\mathcal{A}}{\Fla}$
as to a \emph{parsing table of} $\mathcal{G}$.
Also, we will call \emph{parsing of} $w$ \emph{on} $\pair{\mathcal{A}}{\Fla}$
the application to the string $w$ of the shift-reduce algorithm driven by
the controller $\pair{\mathcal{A}}{\Fla}$.

\section{\SRauta}
\label{sec:srautomata}

In this section, we will define \SRauta, and present their main properties.

Below, we will denote automata with a single final state by a tuple
whose elements represent, respectively,
the set of states,
the vocabulary,
the transition function,
the initial state,
and the final state.
Also, given a set $L$ of symbols, we let $\squared{L}$ represent the set of all
the elements of $L$ surrounded by square brackets.
We call \emph{prospective symbols} the elements of $\squared{L}$.
The intuition behind a prospective symbol like $\squared{x}$ is that
we go across it pretending
that its concrete counterpart $x$ will eventually be found and consumed.

\begin{definition}[\SRauta: layout]
  Let $\pair{\mathcal{A}}{\Fla}$ be a parsing table of
  $\mathcal{G} = (V,T,S,\mathcal{P})$.
  Also, let ${\mathcal{A}}=(\mathcal{Q},V\cup\set{\$},\tauCA,\Pinit,\Pfinal)$.
  Then the
  \emph{\SRauton\ for} $\pair{\mathcal{A}}{\Fla}$
  is the finite state automaton
  $(\mathcal{Q},
    T \cup \set{\$} \mathrel{\cup}
    (\squared{T\cup\set{\$}} \times {\mathcal{Q}} \times {\mathcal{P}}),
    \tauSR,\Pinit,\Pfinal)$
  where $\tauSR$ is defined by the following rules
  \begin{center}
  $\begin{array}{l@{\hspace{7ex}}l}
    \prooftree
        \tauCA\pair{P}{x} = Q
    \justifies
        \tauSR\pair{P}{x} = Q
    \endprooftree
  &  \prooftree
        x\in\Fla\pair{A\rightarrow\beta}{P} ,\quad
        R \in \Fopening{A\rightarrow\beta}{P} ,\quad
        \tauCA\pair{R}{A} = Q
    \justifies
        \tauSR\pair{P}{\trLabel{x}{R}{A\rightarrow\beta}} = Q
    \endprooftree
    \\[2ex]
  \end{array}$
  \end{center}
  with $R \in \Fopening{A\rightarrow\beta}{P}$ iff
  there is a path spelling $\beta$ in $\mathcal{A}$ from $R$ to $P$.
\end{definition}

\begin{figure}
  \centering
  \includegraphics[width=16cm]{FIG1_pic}
\caption{\label{fig:G1}
          Parsing table of ${\mathcal{G}_1}$ \`{a} la Bison (a),
          and corresponding \SRauton\ (b).
          In both structures
          $\Pinit$ is state $0$,
          $p_1$ stands for ${E\rightarrow{E+E}}$, and
          $p_2$ for ${E\rightarrow{a}}$.
          In (a), the dotted line from $1$ to $(p_2,\set{+,\$})$
          means that in state $1$ the lookaheads $+$ and $\$$
          call for a reduction by $p_2$.
          The meaning of $(p_1,\set{+,\$})$ is analogous.
          In (b), labels like $[x_1,x_2]:n:p$ are shorthands for two edges,
          labelled by $[x_1]:n:p$ and by $[x_2]:n:p$, resp..
          }
\end{figure}

For the grammar $\mathcal{G}_1$ with production-set given by
$\set{E\rightarrow{E+E},\, E\rightarrow{a}}$,
Fig.~\ref{fig:G1} shows the instance of $\pair{\mathcal{A}}{\Fla}$
\`{a} la Bison and the corresponding \SRauton.

The language accepted by an \SRauton\ is defined in terms of an
\emph{execution relation}
which describes transitions between configurations.
Each configuration is a quadruple of the shape
$\trConfig{h}{\Qstates}{z}{\Qprod}$ where
$z$ is a string of symbols in $T\cup\set{\$}$,
$\Qstates$ (called state-stack) is a stack that contains states,
$\Qprod$  (called production-stack) is a stack that contains productions,
and $h$ is an auxiliary object to trace which prospective symbol, if any,
was involved in the past transition.
We denote stacks as lists of elements with the top of stack at the rightmost position,
so that $\squared{}$ represents the empty stack.
Also, we use the usual functions \Ftop{\_}, \Fpush{\_}{\_}, and
\FpopN{}{\_}\
on stacks, and let $\FpopN{n}{\Qstates}$ stand for $n$ consecutive applications of
the function ${\rm{pop}}$ to the stack $\Qstates$.

\begin{definition}[\SRauta: execution \& language]
  Let $\mathcal{S}$ be an \SRauton\ with transition function $\tauSR$,
  and initial state $\Pinit$.
  The \emph{language accepted by} $\mathcal{S}$ is given by
  \begin{center}
    $\Flang{\mathcal{S}} =

     \{ w \mid \exists\, \Qstates,\Qprod
          \mbox{ such that }
          \trConfig{\epsilon}{\stacked{\Pinit}}{\epsilon}{\stacked{}} \trArrow^*
          \trConfig{\epsilon}{\Qstates}{w\$}{\Qprod}
          \}$
  \end{center}
  where the \emph{execution relation} $\trArrow$
  is defined by the following rules
  \begin{center}
  $\begin{array}{c}
    \prooftree
        \Ftop{\Qstates}=P , \quad
        \tauSR\pair{P}{x} = Q ,\quad
        h \in \set{\epsilon,\squared{x}}
    \justifies
        \trConfig{h}{\Qstates}{w}{\Qprod} \trArrow
        \trConfig{\epsilon}{\Fpush{Q}{\Qstates}}{wx}{\Qprod}
    \using
        (S)
    \endprooftree
  \\[4ex]
    \prooftree
        \Ftop{\Qstates}=P , \quad
        \tauSR\pair{P}{\trLabel{x}{R}{A\rightarrow\beta}} = Q  ,\quad
        \QstatesPrime = {\FpopN{\size{\beta}}{\Qstates}} , \quad
        \Ftop{\QstatesPrime} =R , \quad
        h \in \set{\epsilon,\squared{x}}
    \justifies
        \trConfig{h}{\Qstates}{w}{\Qprod} \trArrow
        \trConfig{\squared{x}}{\Fpush{Q}{\QstatesPrime}}{w}{\Fpush{A\rightarrow\beta}{\Qprod}}
    \using
        (R)
    \endprooftree
  \end{array}$
  \end{center}
\end{definition}

Rule (S) in the definition of $\trArrow$ mimics the execution of a shift move
of the shift-reduce algorithm.
Here we just observe two facts.
First, $h$ is required to be either empty or the prospective version
of the symbol which triggers the execution step.
Second, when $h$ actually equals $\squared{x}$, the application of rule (S)
obliterates the tracing of $\squared{x}$ in the reached configuration.
Hence, an execution step involving a prospective symbol $\squared{x}$ can never be followed
by a step depending on some $\tauSR\pair{P_n}{x'}$ with ${x'}\neq{x}$.
Also, the tracing of a prospective symbol stops once its concrete version
is met.
Rule~(R) simulates the execution of a reduce move, with the prospective symbol
$\squared{x}$ playing the lookahead $x$ that calls for the reduction.
Notice that the application of the (R) rule traces $\squared{x}$
in the first component of the new configuration.
Moreover, by the premiss $h \in \set{\epsilon,\squared{x}}$, an execution step
depending on the prospective symbol $\squared{x}$ can never be followed by
a step depending on $\squared{x'}$ if ${x'}\neq{x}$.
Overall, the intuition behind the use of prospective symbols in \SRauta\
is that once a symbol $\squared{x}$ starts playing as lookahead for a reduction,
it keeps doing so until an application of the (S) rule actually consumes
$\squared{x}$ in the first component of the configuration, and appends $x$
to the word under construction.

Next, we present a result on the correspondence between the execution of the
shift-reduce algorithm and the execution of \SRauta.

\begin{theorem}
\label{th:tableAndSR}
  Let $\mathcal{S}$ be the \SRauton\ for the parsing table
  $\pair{\mathcal{A}}{\Fla}$ of $\mathcal{G}$.
  Also, let $\Pinit$ be the initial state of $\mathcal{S}$.
  Then the following holds.
  \begin{itemize}
  \item
    If, for some local resolution of possible conflicts,
    the parsing of $w$ on $\pair{\mathcal{A}}{\Fla}$ is successful
    and returns $\Ftree{w}$ then,
    for some $\Qstates$,
    $\trConfig{\epsilon}{\stacked{\Pinit}}{\epsilon}{\stacked{}} \trArrow^*
     \trConfig{\epsilon}{\Qstates}{w\$}{\Ftree{w}}$.
  \item
    If, for some $\Qstates$ and some $\Qprod$,
    $\trConfig{\epsilon}{\stacked{\Pinit}}{\epsilon}{\stacked{}} \trArrow^*
     \trConfig{\epsilon}{\Qstates}{w\$}{\Qprod}$
    then, for some local resolution of possible conflicts,
    the parsing of $w$ on $\pair{\mathcal{A}}{\Fla}$ is successful
    and $\Ftree{w}=\Qprod$.
  \end{itemize}
\end{theorem}

\begin{pf}
  The first statement is proved by induction on the number of steps performed
  by the shift-reduce algorithm.
  The inductive handle is based on the following facts.
  Each move of the shift-reduce algorithm is matched by an execution step of
  the \SRauton, and the state-stack of the automaton evolves exactly as the parsing
  auxiliary stack.
  Also, at each move, the word-component of the configuration reached by the
  automaton equals the portion of input already processed by the shift-reduce
  algorithm, and the production-stacks of the two executions grow in lockstep
  fashion.

  In proving the second statement,
  care has to be taken to ensure that, if the \SRauton\ performs a step which involves
  either $x$ or $\squared{x}$, then the symbol $x$ is actually what the
  shift-reduce algorithm gets from its input buffer.
  To get the required guarantees, the statement is proven by induction on the
  length of \SRauta\ executions whose latest step is obtained by an application
  of rule~(S), which
  is the case, indeed, for executions leading to
  $\trConfig{\epsilon}{\Qstates}{w\$}{\Qprod}$.
  By the definition of $\trArrow$,
  if the execution step is inferred by rule~(S) and depends
  on an $x$-transition of the automaton, then $x$ shows as suffix of the
  word-component of the reached configuration.
  Suppose now that
  the execution step is deduced by rule~(R),
  that it involves $\squared{x}$, and
  that the word-component
  of the current configuration is $w$.
  If this is the case, then by the properties of $\trArrow^*$ described above,
  $x$ is the symbol that is appended to $w$ at the first (S)-step along the execution.
  As for the rest, the inductive handle is dual to that used in the proof
  of the first statement.
  It keeps track of the correspondence between pairs of stacks,
  and between the word-component of configurations and the word
  consumed by the shift-reduce algorithm.
\end{pf}

Cor.~\ref{cor:tableAndSR} below is an immediate consequence of
Th.~\ref{th:tableAndSR}.

\begin{corollary}
\label{cor:tableAndSR}
  Let $\mathcal{S}$ be the \SRauton\ for the parsing table
  $\pair{\mathcal{A}}{\Fla}$ of $\mathcal{G}$.
  Then $\Flang{\mathcal{S}}=\Flang{\mathcal{G}}$.
\end{corollary}

We conclude this section by a comment on nondeterminism.
As the proof of Th.~\ref{th:tableAndSR} hints, the nondeterminism of parsing
tables is reflected in \SRauta\ in a precise sense.
Suppose that the state $P$ contains a conflict on $x$.
If, during an execution of the \SRauton, $P$ is on top of the state-stack
when the current word is $w$, then there are two distinct ways
to reach a configuration for the word $wx$ by going along the distinct branches
outgoing $P$.

\section{Ambiguity detection}
\label{sec:detection}

In this section, we will present the proposed strategy for ambiguity detection.

The activity is carried on alternating two sorts of phases:
guessing and validation.
In the guessing phase, relying upon an approximation of \SRauta,
we identify words -- if any -- that might show the ambiguity of the grammar.
In the subsequent phase, we validate the paths associated with these words
against proper executions of \SRauta.

A grammar $\mathcal{G}$ is ambiguous iff there exists a word in $\Flang{\mathcal{G}}$
that has two distinct rightmost derivations, or, equivalently,
two distinct leftmost derivations.
The next result, that underpins the proposed detection strategy,
characterizes ambiguity in terms of executions of \SRauta.

Below, given any configuration $\Nconfig=\trConfig{h}{\Qstates}{w}{\Qprod}$,
we say that two execution steps from $\Nconfig$
\emph{are in conflict on $x$} to mean that
$P=\Ftop{\Qstates}$ has a conflict on $x$ and one of the following scenarios apply:
\emph{(i)} both the execution steps are inferred by rule~(R) and
  depend, respectively, on some
  $\tauSR\pair{P}{\trLabel{x}{R'}{p'}}$ and on some
  $\tauSR\pair{P}{\trLabel{x}{R''}{p''}}$
  such that $p' \neq {p''}$;
\emph{(ii)} one of the execution steps is inferred by rule~(S) and depends on
  $\tauSR\pair{P}{x}$, and the other is inferred by rule~(R) and depends on
  some $\tauSR\pair{P}{\trLabel{x}{R}{p}}$.

\begin{theorem}
\label{th:ambiguity}
  Let $\mathcal{S}$ be the \SRauton\ for the parsing table
  $\pair{\mathcal{A}}{\Fla}$ of $\mathcal{G}$.
  Also, let $\Pinit$ be the initial state of $\mathcal{S}$, and $\tauSR$
  be its transition function.
  Then $\mathcal{G}$ is ambiguous iff
  $w$ exists such that

  $\trConfig{\epsilon}{\stacked{\Pinit}}{\epsilon}{\stacked{}} \trArrow^*
   \Nconfig$
  and
  $ \Nconfig \trArrow
    \NconfigPrime \trArrow^*
    \trConfig{\epsilon}{\Qstates_{1}}{w\$}{\Qprod_{1}}$
  and

  $  \Nconfig \trArrow
    \NconfigDouble \trArrow^*
    \trConfig{\epsilon}{\Qstates_{2}}{w\$}{\Qprod_{2}}$

  for some
  $\Qstates_{1},\Qprod_{1}$,
  $\Qstates_{2},\Qprod_{2}$,
  $\Nconfig,\NconfigPrime,\NconfigDouble$
  such that
  $\Nconfig \trArrow \NconfigPrime$ and $\Nconfig \trArrow \NconfigPrime$
  are in conflict on $x$.
\end{theorem}

\begin{pf}
(If)
If $\mathcal{G}$ is ambiguous then there exists $w\in\Flang{\mathcal{G}}$
that has two distinct rightmost derivations.
Hence by Th.~\ref{th:tableAndSR},
letting $\Pinit$ be the initial state of $\mathcal{S}$,
$\trConfig{\epsilon}{\stacked{\Pinit}}{\epsilon}{\stacked{}} \trArrow^*
 \trConfig{\epsilon}{\Qstates_{1}}{w\$}{\Qprod_{1}}$
and
$\trConfig{\epsilon}{\stacked{\Pinit}}{\epsilon}{\stacked{}} \trArrow^*
 \trConfig{\epsilon}{\Qstates_{2}}{w\$}{\Qprod_{2}}$
for some $\Qstates_{1},\Qstates_{2},\Qprod_{1},\Qprod_{2}$
with
$\Qprod_{1}\neq\Qprod_{2}$.
By $\Qprod_{1}\neq\Qprod_{2}$, the two executions above must differ at least for
one step inferred by the $(R)$-rule.
Since both executions lead to configurations with the same word-component,
the steps of the two executions are inferred from transitions of the
\SRauton\ involving the same sequence of symbols in $T\cup\set{\$}$.
Hence, the two executions must be made of zero or more equal steps up to
a configuration with a state $P$ at the top of the
state-stack that contains a conflict on some $x$.
From that configuration, the two executions must continue with distinct
steps that are in conflict on $x$.
\\
(Only if)
By Cor.~\ref{cor:tableAndSR}, $w\in\Flang{\mathcal{G}}$, and
by Th.~\ref{th:tableAndSR} both $\Qprod_{1}$ and $\Qprod_{2}$ represent
derivation trees for $w$.
It remains to show that $\Qprod_{1} \neq \Qprod_{2}$.
Assume $\Nconfig=\trConfig{h}{\Qstates}{w_1}{\Qprod}$.
If both $\Nconfig \trArrow \NconfigPrime$ and $\Nconfig \trArrow \NconfigDouble$
are inferred by the (R)~rule, then the production-stacks of
$\NconfigPrime$ and of $\NconfigDouble$ are obtained by pushing distinct
productions on $\Qprod$.
Nothing is popped out of production-stacks during execution,
hence the thesis.
Suppose now that $\Nconfig \trArrow \NconfigPrime$ is inferred by the (S)~rule,
and $\Nconfig \trArrow \NconfigDouble$ by the (R)~rule, and let
$A\rightarrow\beta$ be the production involved in the inference of
$\Nconfig \trArrow \NconfigDouble$.
Then, $w$ has the form $w'_{1}w''_{1}$ for some $w''_{1}$ that
is the frontier of the subtree rooted at $A$ in the tree described by $\Qprod_2$.
This is not the case for $w''_{1}$ in the tree represented by $\Qprod_1$.
Hence $\Qprod_{1} \neq \Qprod_{2}$.
\end{pf}

The labelled transition relations defined below are used to get approximations
of the language recognized by \SRauta.

\begin{definition
  Let $\mathcal{S}$ be the \SRauton\ for the parsing table
  $\pair{\mathcal{A}}{\Fla}$ of $\mathcal{G}$.
  Also, let $\tauSR$ be the transition function of $\mathcal{S}$.
  For every pair of states $P$ and $Q$ of $\mathcal{S}$,
  $P \sArrow{x} Q$ iff $\tauSR\pair{P}{x} = Q$, and
  $P \sArrow{\squared{x}} Q$ iff $\tauSR\pair{P}{\trLabel{x}{R}{p}} = Q$
  for some $R$ and some $p$.
  Also,
  $\dArrow{x}$ stands for $\sArrowSqStar{\squared{x}} \sArrow{x}$, and
  $\dArrowWord{w}$ stands for $\dArrow{x_1}\ldots\dArrow{x_j}$
  for $w=x_1\ldots{x_j}$.
\end{definition}

To detect ambiguity, we analyze one conflict at a time, and look for words
that are accepted along paths taking either branch out of the conflict state.
The analysis is applied to all the conflicts of the \SRauton\ and searching
for longer and
longer words, up to the point that either we can conclude that the grammar is
ambiguous or unambiguous,
or a fixed bound on the length of the searched words is reached.
When analyzing a certain conflict of state $P$,
we assume that all the conflicts of the states other than $P$ are switched off
by applying a combination of resolutions for them.
If the analysis of the conflict of $P$ is inconclusive,
the analysis is retried for a different combination of resolutions for the
other conflicts.

The search for words that might have distinct derivations is carried on
alternating guessing and validation phases as described below.
In the guessing phase, we make use of the function $\Fguess{P}{Q}{l}$ that
returns the set of words $w$ shorter than $l$ and such that
$P\dArrowWord{w}Q$.
The validation phase checks whether an execution meeting specified
requirements exists.
If an execution from $\Nconfig$ to $\Nconfig'$ exists, where
$\Nconfig'$ is a configuration with $P$ at the top of its state-stack and with
$w$ as word-component, then the invocation of $\Fvalidate{\Nconfig}{w}{P}$
returns $\Nconfig'$, otherwise it returns failure.

For clarity, we first describe the main principles of the analysis of a
single conflict.
Then we comment on how inconclusive searches are handled.
We assume that the \SRauton\ at hand
has initial state $\Pinit$, and
final state $\Pfinal$.
Also, we let
$\Nconfig_0=\trConfig{\epsilon}{\stacked{\Pinit}}{\epsilon}{\stacked{}}$,
and let $l_1,l_2$ be integers.
We first consider the case that the state $P$ has an r/r conflict for $x$.
By Th.~\ref{th:ambiguity}, we focus on pairs of paths with the following shape
\begin{equation}
\label{eq:rr}
   \Pinit
    \dArrowWord{w_1} R
    \sArrowSqStar{\squared{x}}
    P
    \sArrow{\squared{x}} Z_1
    \dArrow{x} Q_1
    \dArrowWord{w_2\$} \Pfinal

    \quad

   \Pinit
    \dArrowWord{w_1} R
    \sArrowSqStar{\squared{x}}
    P
    \sArrow{\squared{x}} Z_2
    \dArrow{x} Q_2
    \dArrowWord{w'_2\$} \Pfinal
\end{equation}
where $Z_1$ and $Z_2$ are inferred by transitions of the automaton involving
$\squared{x}$ and two distinct productions $p_1$ and $p_2$.
We notice here that there are as many plausible instances of
$Z_i$ meeting the above requirements as the size of $\Fopening{p_i}{P}$.
To save on validation failures, we operate as follows.
\begin{enumerate
\item
    For each $R$ such that $R\sArrowSqStar{\squared{x}}P$,
    we invoke $\Fguess{\Pinit}{R}{l_1}$.
    So, we can collect a set of triples
    $\triple{\Pinit}{w_1}{R}$ such that
    $\Pinit\dArrowWord{w_1}R$.
    Call \NsetOne\ such set.
\item
    For each triple $\triple{\Pinit}{w_1}{R}$ in \NsetOne, we invoke
    $\Fvalidate{\Nconfig_0}{w_1}{R}$.
    Call \NsetTwo\ the set of configurations obtained in this way.
    We use \NsetTwo\ to decide which are the most appropriate targets
    to consider among the $\squared{x}$-transitions outgoing $P$
    in (\ref{eq:rr}).
    To do that, we select the configurations in \NsetTwo\ that can undergo
    the following manipulation.
    We attempt to prolong the execution from each configuration in \NsetTwo\
    by performing zero or more steps driven by the (R)~rule under $\squared{x}$
    so to reach a configuration with $P$ on top of the state-stack.
    Then, by executing steps driven by the (R)~rule
    for $p_1$ and, resp., by the (R)~rule for $p_2$, we get configurations
    with $Z_i$ on top of the state-stack, with $i=1,2$.
    Next, we extend these executions further by means of zero or more steps driven by
    the (R)~rule under $\squared{x}$, and then by a step driven by the (S)~rule for $x$.
    So, from those configurations in \NsetTwo\ which can be extended as described
    above, we obtain pairs of configurations reachable from $\Nconfig_0$
    that have $w_1{x}$ as word-component and $Q_i$ at the top of their state-stacks.
    Call \NsetThree\ the set of these pairs.
\item
    For each pair $\pair{\Nconfig_1}{\Nconfig_2}$ in \NsetThree\
    we do the following.
    Suppose $Q_i$ is on top of the state-stack of $\Nconfig_i$.
    For each $w'\in\Fguess{Q_1}{\Pfinal}{l_2}$, we check whether
    $Q_2\dArrowWord{w'}\Pfinal$.
    If so, we run both
    $\Fvalidate{\Nconfig_1}{w'}{\Pfinal}$ and
    $\Fvalidate{\Nconfig_2}{w'}{\Pfinal}$.
    If both validations are successful, then the returned configurations
    have word-components $w_1{x}w'$ with $w'=w_2\$$ for some $w_2$.
    Also, their production-stacks
    represent two distinct derivation trees for $w_1{x}w_2$.
    Hence the grammar is ambiguous.
\end{enumerate}

Above, we streamlined the search strategy.
It remains to comment on the scenarios that induce us either to retry the analysis with
longer words, or to give up, or to conclude that the grammar is unambiguous.
They are identified as follows.
If either $\NsetOne$ or $\NsetTwo$ or $\NsetThree$ is empty, and if $l_1$ can be
increased further, then we try again from the beginning searching longer guesses for $w_1$.
Analogously, if either $\Fguess{Q_1}{\Pfinal}{l_2}$ is empty,
or no $w' \in \Fguess{Q_1}{\Pfinal}{l_2}$ is such that $Q_2\dArrowWord{w'}\Pfinal$,
or no $w' \in \Fguess{Q_1}{\Pfinal}{l_2}$ can be validated from both
$\Nconfig_1$ and $\Nconfig_2$,
then we can reuse $\NsetThree$ and retry with longer guesses for $w_2$.
This is reasonable, however, only under some circumstances.
Indeed, if all the possible guesses for $w_1$ and for $w_2$ have been computed
(and hence all the possible instances of $R$, $Z_1$ and $Z_2$ have been considered),
and if either the analyzed conflict is the single conflict of the grammar,
or analogous circumstances apply to all the conflicts of the grammar,
then we conclude that the grammar is unambiguous.

In case the state $P$ has an s/r conflict for $x$,
the relevant pairs of paths have the following shape
\begin{equation}
\label{eq:sr}
   \Pinit
    \dArrowWord{w_1} R
    \sArrowSqStar{\squared{x}}
    P
    \sArrow{x} Q_1
    \dArrowWord{w_2\$} \Pfinal

    \qquad\qquad

   \Pinit
    \dArrowWord{w_1} R
    \sArrowSqStar{\squared{x}}
    P
    \sArrow{\squared{x}} Z
    \dArrow{x} Q_2
    \dArrowWord{w'_2\$} \Pfinal
\end{equation}
and the analysis is carried on analogously to the case of an r/r conflict.
Shortly, we compute guesses for $w_1$ from $\Pinit$ to $R$,
then we validate the guesses against proper executions from $\Pinit$ to $R$,
and get extensions to $Q_1$ and to $Q_2$.
Next, we compute guesses for $w_2$ from $Q_1$ to $\Pfinal$,
then check whether they could, at least approximately, be matched from $Q_2$.
If so, we run the validations for $w_2$ from configurations whose
state-stacks have $Q_1$ and $Q_2$ at their top.

We conclude the section by playing the proposed strategy for the s/r
conflict on $\mathop{+}$ in state $5$
of the \SRauton\ for $\mathcal{G}_1$ (Fig.~\ref{fig:G1}).
Using the naming in (\ref{eq:sr}), $R$ ranges over $\set{1,5}$.
For $l_1=4$, we get
\begin{center}
  $\NsetOne=\set{a,a\mathop{+}a}$
\end{center}
and, by validation,
\begin{center}
$\NsetTwo=\{
  \langle {\epsilon},
          {\stacked{0,1}},
          {a},
          {\stacked{}}
  \rangle,
  \langle {\epsilon},
          {\stacked{0,2,4,1}},
          {a\mathop{+}a},
          {\stacked{p_2}}
  \rangle
  \}$.
\end{center}
The manipulation of $\trConfig{\epsilon}{\stacked{0,1}}{a}{\stacked{}}$ fails,
and we are left with
\begin{center}
$\NsetThree=\{
  (
  \trConfig{\epsilon}{\stacked{0,2,4,5,4}}{a\mathop{+}a\mathop{+}}{\stacked{p_2,p_2}},
  \trConfig{\epsilon}{\stacked{0,2,4}}{a\mathop{+}a\mathop{+}}{\stacked{p_2,p_2,p_1}}
  )
  \}$.
\end{center}
Next, we compute guesses for $l_2=l_1$ from state $4$ to state $3$.
We obtain $a\$$ and run its validations from the configurations paired in
$\NsetThree$.
By that, we get
\begin{center}
$  \langle  {\epsilon},
            {\stacked{0,2,3}},
            {a\mathop{+}a\mathop{+}a\$},
            {\stacked{p_2,p_2,p_2,p_1,p_1}}
            \rangle$,
and
$  \langle  {\epsilon},
            {\stacked{0,2,3}},
            {a\mathop{+}a\mathop{+}a\$},
            $ $
            {\stacked{p_2,p_2,p_1,p_2,p_1}}
            \rangle$
\end{center}
that show the ambiguity of $\mathcal{G}_1$.

\section{Conclusions}
\label{sec:conclusions}

Starting from LR parsing tables, we defined \SRauta,
and used them to describe a conflict-driven strategy
to detect grammar ambiguity.
Through prospective symbols, lookaheads are accommodated on the edges of
\SRauta.
This feature was crucial to mine words in the language as paths on labelled graphs.

The reported strategy showed to be a quite handy way of reasoning about the ambiguity
of small grammars of scholarly size.
The assessment of its effectiveness for large grammars,
as well as comparisons with other detection methods,
is subject to
further investigation.
Other directions for future work are relative to possible applications of
\SRauta\ in testing the adequacy of the heuristics used by
parser generators to handle nondeterministic grammars.