11institutetext: Swinburne University of Technology, Victoria 3122, Australia

# Working mechanism of Eternalblue and its application in ransomworm

Zian Liu

###### Abstract

After the leaking of exploit Eternalblue, some ransomworms utilizing this
exploit have been developed to sweep over the world in recent years.
Ransomworm is a global growing threat as it blocks users’ access to their
files unless a ransom is paid by victims. Wannacry and Notpetya are two of
those ransomworms which are responsible for the loss of millions of dollar,
from crippling U.K. national systems to shutting down a Honda Motor Company in
Japan. Many dynamic analytic papers on Wannacry were published, however,
static analytic papers about Wannacry were limited. Our aim is to present
readers an systematic knowledge about exploit Eternalblue, from a high–leveled
semantic view to the code details. Specifically, the working mechanism of
Eternalblue, the reverse engineering analysis of Eternalblue in Wannacry, and
the comparison with the Metasploit’s Eternalblue exploit are presented. The
key finding of our analysis is that the code remains almost the same when
Eternalblue is transplanted into Wannacry, which indicates its potential for
signatures and thus detection.

###### Keywords:

Cyber Threat Ransomworm Static Analysis Wannacry

##  1 Introduction

With computers and networks being applied more and more widely in daily life,
enterprise and organizations tend to store large scale data digitally.
However, those information management systems often contain vulnerabilities
and are prone to be exploited by hackers. In May 2017, a ransomworm called
Wannacry bursts out worldwide. It caused massive infection and enormous
economic losses by infecting various industrial and government internal
networks, such as UK’s National Health Service and etc [2]. The average attack
the other organizations suffer is 14,300 per day according to [6]. It is
reported to derive from an NSA exploit tool [15]. Once Wannacry infects a
system, it encrypts copies of various file types and deletes the originals.
The encrypted files cannot be accessed without a decryption key.

A lot of work has been done to analyze Eternalblue and Wannacry. Most of the
papers on Wannacry focused on the dynamical analysis. D.Y. KAO et al. analyzed
Wannacry dynamically, from the aspects of process name, Registry, file system,
and Network activity, respectively. They also applied the features to these
aspects to create Yarra rules for pattern-matching detection [9]. Qian et al.
also dynamically analyzed Wannacry for testing the performance of an automatic
dynamical analysis tool [7]. As to the static analysis, D.Y. KAO et al.
provided a detailed analysis based on different phases. Critical files and
strings participating in those phases were highlighted [10]. Hirokazu
statically analyzed Wannacry based on the Eternalblue and DoublePulsar
modules. He also applied the discoveries into Snort rules to defend future
network attacks based on those two modules [11].

Even though those works helped investigate the working mechanism of Wannacry
and Eternalblue, there lacks the study on the comparison between Wannacry’s
Eternalblue module and the original Eternalblue module. To bridge this
research gap, we proceed with our analysis by first studying the exploit’s
working mechanism that applied in Wannacry. Then we use code analytic tools
and network capture tools to compare Wannacry’s Eternalblue module and the
original Eternalblue module. After a detailed study, we find that the exploit
utilized in Wannacry shares a very similar pattern to the original exploit,
which can be used as features for signature extraction.

The remainder of this paper is organized as follows. In section 2, the
original Eternalblue module’s working mechanism is introduced. Section 3
analyzes the Eternlablue module in Wannacry and Section 4 concludes this
paper.

##  2 Eternalblue’s working mechanism in Metasploit

Assume we have two computers: an attacking machine and a victim machine. At
the very beginning, Eternalblue is a piece of code on the attacking machine.
Once executed, it will send multiple SMB (Server Message Block) requests to
the victim machine through the SMB protocol. As a result, the victim machine
must respond to these requests. In this SMB communication phase, the attacking
machine plays the role of client and the victim machine plays the role of
server, which is the reason we refer them to attacking machine and victim
machine respectively. Among these SMB requests, the Transaction SMB commands
are essential because they are utilized to tamper the data on the server
(victim) with a buffer overflow bug, which further leads to the execution of
the ransomworm on the victim machine.

Hence, prior to introducing details of the working mechanism of Eternalblue,
in this section we will firstly introduce the normal usage of Transaction SMB.
According to MSDN [3], Transaction SMB commands enable the client to access
advanced features on the server. Specifically, the three transaction messages
are:

  * •

SMB_COM_TRANSACTION (or Trans),

  * •

SMB_COM_TRANSACTION2 (or Trans2),

  * •

SMB_COM_NT_TRANSACT (or NT Trans).

It is also noted in [4] that, SMB_COM_NT_TRANSACT subcommands enable the
transfer of very large data chunks. And SMB_COM_TRANSACTION2 subcommands
provide richer file system services such as allowing clients to set and
retrieve Extended Attribute key/value pairs, to make use of long file names,
and to perform directory searches, etc.

The information above summarizes the legitimate usage of the Transaction SMB
commands. However, in Eternalblue, they are not applied for the original
legitimate purposes, but for a buffer overflow bug. Specifically, when
responding to these crafted requests, the server will convert the payload
contained in these requesting Transaction SMB packets, i.e., the original
Os2Fea [1] list, to the currently used NtFea [1] format (result type), as
Os2Fea (the original type) is outdated [12]. The NtFea list will be stored
into a result list buffer. This process is also referred to the conversion
process. Under some mild conditions, the server can be fooled by allocating a
result list buffer smaller than the NtFea list to be stored. Thus the NtFea
list can overwrite the next buffer. And the original list with a specific
length will satisfy such mild conditions.

In more detail, the “next buffer” is a Srvnet.sys [1] buffer, which is
allocated on the server for the attacker’s SMB request. Once allocated, this
buffer will wait for another data package to be sent to the server. There are
two parameters in the header of this Srvnet.sys buffer: one decides where to
map the data package on this server upon receiving the data package and
another decides what function to execute when the Srvnet connection is
disconnected. So if these two parameters are modified to the same address, the
payload will be mapped and be executed upon closing the connection.

To trigger the overflow of Srvnet.sys and thus inject the malicious codes to
the victim, Eternalblue covers three essential steps: crafting original list,
buffer grooming, and sending the payload. We proceed our discussion of
Eternalblue by first showing a high-level description of the three steps, then
dive into details of each step.

From a high-level point of view, in step crafting original list, an original
list is crafted. In the second step, multiple grooming packages are sent in a
deliberate order which changes the server’s buffer status to a point that is
vulnerable to overflow. Then, sending the complete original list results in
the overflow. In the final step, the payload is sent to the server’s
Srvnet.sys buffer. Because of the overflow, the payload can be mapped to the
desired location and executed upon closing the connection.

###  2.1 Crafting original list

To understand crafting of the original list, we firstly recall the normal
conversion process on the server machine.

As shown in Algorithm 1, in the Os2Fea format, there is a parameter ULONG
SizeOfList prior to the actual records describing the total bytes of the
original list.

The server’s legitimate conversion process is shown in Algorithm 2. In step
Compute S1, the algorithm will go through the original list and discard the
records that exceed the boundary set by SizeOfList, and the remaining original
list (Os2Fea) size is S2, as shown in Fig. 1. S1 is the result list (NtFea)
size corresponding to the remaining original list with size S2. Hence, in the
third line of Algorithm 2, the server allocates the result list buffer with
size S1.

Back into the second line of Algorithm 2, S2 needs to be assigned to the
original list’s parameter SizeOfList, as this parameter will be used later in
the while loop. In the while statement of Algorithm 2, the server calls a
subfunction repeatedly to convert the original list block by block and stores
the result list into this result list buffer. The number of the loop is
determined by the SizeOfList’s value. The original_list_initial_address in
this algorithm points to the beginning of the original list. It is later
assigned to variable Current_pointer, which will increase after each
iteration.

Above is the server’s conversion process. The bug occurs when assigning S2 to
the original list’s parameter SizeOfList if the SizeOfList is no less than
$2^{16}$ (0x10000 in hexadecimal) and the actual original list’s record
exceeds the boundary set by SizeOfList [13], like shown in Fig. 1.

In more detail, when parsing S2 to SizeOfList, only the LOWORD (low-order
word) bytes of the DWORD (double word) variable SizeOfList is updated because
of a wrong casting instruction. Hence the End_pointer in Algorithm 2 will be
miscalculated, which leads to an unexpected conversion time. This corresponds
to a different time to execute the while statement in Algorithm 2. For
example, as occurred in this Eternalblue exploit, the SizeOfList is initiated
with 0x10000. After discarding, the remaining original list size S2 is 0xff5d.
However, when executing the second line of Algorithm 2 (i.e., assigning S2 to
SizeOfList), only the LOWORD bytes of SizeOfList is updated, which turns
SizeOfList from 0x10000 to 0x1ff5d rather than 0xff5d, hence enlarge this
SizeOfList.

Algorithm 1 Os2Fea list structure

$Struct\ Os2FeaList\\{$

$ULONG\ SizeOfList$

$UCHAR\ Os2FeaList\lceil SizeOfList-4\rceil$

$\\}$

Algorithm 2 The legitimate server’s conversion process

$Compute\ S1$

$S2\ assigned\ to\ SizeOfList\ $

$Allocate\ buffer\ (result\ list\ buffer)\ with\ size\ S1$

$End\\_pointer=original\\_list\\_initial\\_address+SizeOfList$

$Current\\_pointer=original\\_list\\_initial\\_address$

while Current_pointer<End_pointer do

$convert(Current\\_pointer)$

$Current\\_pointer+=each\\_record\\_size$

end while

Figure 1: Server discards the out-of-boundary records and calculates the
result list size (S1) based on the remaining records

Based on the discussion above, the crafted list is as follows. The forged
original list is of the Os2Fea type, its parameter SizeOfList is with value
$2^{16}$ (0x10000 in hexadecimal), followed by a list of Os2Fea data, as
demonstrated in Algorithm 1. There are 607 pieces of data included in this
crafted list and garbage data at the end which confines the request packet to
a particular size. The first 605 pieces of records are empty, the 606th record
is not empty and can be filled with arbitrary data of a certain length. The
607th record contains the fake Srvnet.sys header and this 607th record exceeds
the boundary set by SizeOfList [12]. As analog in Fig. 1, the 607th record is
the black section, followed by some garbage data. After discarding, only the
first 606 records should be converted.

When converting this crafted list on the server, as demonstrated in Algorithm
2, after discarding, S1 and S2 are calculated representing the first 606
records of the result list and the original list. Then, the SizeOfList should
be assigned to S2 but in fact assigned to an enlarged value because of the
wrong casting (assigned 0x1ff5d rather than 0xff5d). Hence the End_pointer is
also enlarged. Afterwards, the result list buffer that can only store the
first 606 result records will be allocated. Later, the conversion begins, and
the loop will be executed for extra times as the End_pointer is enlarged.
Hence the server will convert and store 607 records in the buffer for 606
records. This is the reason why this 607th record shall be crafted with a
forged Srvnet.sys buffer header and the preceding records can be filled with
arbitrary data of a certain size.

As mentioned earlier, once the Srvnet.sys buffer is allocated on the server,
it waits for another data packet. There are two critical fields in the
Srvnet.sys buffer header for processing the data packet: one is called memory
descriptor list (MDL) which points to a virtual address that the data package
shall be mapped to once received； the other one is called pSrvNetWskStruct. It
points to a function which shall be called when the Srvnet connection is
closed. Therefore, overwriting these two fields with the same address can make
the server map the shellcode to the desired location and execute the shellcode
after closing the Srvnet connection.

Finally, it should be noted that the crafted data in the 607th record should
be differentiated from the shellcode since the crafted 607th record is used to
overwrite the Srvnet.sys buffer’s header, which paves the way for sending the
shellcode. The sending process of the shellcode is to be discussed later.

###  2.2 Buffer grooming

We have discussed how the crafted list will lead to the buffer overflow in
Srvnet.sys. If the buffer Srvnet.sys is not allocated exactly after the result
list buffer, the attack fails. This buffer grooming process aims to improve
the success rate of overflowing the Srvnet.sys buffer. Table. 1 shows all the
grooming packages sent by Eternalblue in timeline. We have validated the
packets by analyzing the packets sent by the samples from 2 sources [14] and
[8]. The ultimate goal of the grooming procedure is to make the server
allocate a Srvnet.sys buffer immediately following the result list buffer.
Only when this goal is achieved, the excessive data from the result list
buffer can overwrite the Srvnet.sys buffer’s header later. The order of the
packages sent in Table. 1 can increase the possibility of achieving our
ultimate goal. However, the proof is complicated and out of the scope of this
paper.

Table 1: Eternalblue package sent in timeline No. | Type | Description
---|---|---
1 | Srv |  | Anonymous login and IPC$ tree connect, then send the crafted original list
---
except the last segment to the server through an NT Trans Request and
multiple Trans2 Secondary Requests. An Echo package is followed to ensure the
list was sent successfully.
2 |  | 1st
---
reserve
| Send malformed Negotiate Protocol Request and Session Setup AndX Request
---
to reserve buffer (0x10000 bytes) with size smaller than the result list
buffer in
NonPagedPool on the server.
3-15 | Srvnet |  | Send multiple TCP packages to establish Srvnet connections which fill up the
---
slot before the result list buffer.
16 |  | 2nd
---
reserve
| Send malformed Negotiate Protocol Request and Session Setup AndX Request
---
to reserve buffer (0x11000) slightely bigger than the result list buffer. This
reserved buffer serves as a place holder for the result list buffer.
2 |  | 1st
---
reserve
| Send a FIN TCP package to free the 1st reserved buffer.
---
17-22 | Srvnet |  | Send TCP packages to establish extra Srvnet connections. One of them is
---
expected to be allocated next to the 2nd reserved buffer.
16 |  | 2nd
---
reserve
| Send a FIN TCP package to free the 2nd reserved buffer.
---
1 | Srv |  | Send the last segment of the original list through a Trans2 Secondary Request.
---
So the Srv.sys will convert the list. To store the result list with size
0x10fe8
(S1), the server allocates 0x11000 bytes. Because of Windows memory’s
last-in-first-out working fasion, the 2nd reserved buffer just being freed
should
be allocated here.
| 3-15 and
---
17-22
Srvnet |  | Send the shellcode through Mutiple TCP packages. The overflow ensures the
---
shellcode be mapped to a desired location. Then close the connections.

The following paragraphs introduce the packages sent in each step listed in
Table. 1. To validate the buffer grooming process, we reproduce the spreading
process in a virtual environment and check the captured network packages
listed in Table. 1. The samples are created based on scripture on the exploit-
db website [14] and Metasploit Eternalblue module [8]. The baseline of the
virtual environment and experiment tools are shown below:

  * •

Virtual Machine: VMWare Workstation

  * •

Client (attacker) machine OS: Windows 7 x64 SP1

  * •

Client (attacker) machine IP address: 10.10.10.151

  * •

Server (victim) machine OS: Windows 7 x64 SP1

  * •

Server (victim) machine IP address: 10.10.10.152

  * •

Analysis tools: Wireshark

Firstly the exploit from the client (attacker) machine establishes a
connection and determines the target operating system’s version and
architecture based on the SMB and DCE/RPC (Distributed Computing Environment /
Remote Procedure Calls [5]) reply, respectively. Figure. 2 shows the server
(victim) machine’s buffer initial status before receiving any packages from
the client (attacker) machine.

Figure 2: Server machine’s buffer initial status

Then the exploit sends the original list to the target machine through
connection No.1. However, the legitimate usage of the Transaction SMB request
is to send Trans2 Secondary Request after Trans2 Request or to send the NT
Trans Secondary Request after the NT Trans Request. Here in this exploit, the
purpose of sending Trans2 Secondary Requests packets after the initial NT
Trans Request is to utilize another data parsing bug, which permits the
attacker to send the payload in a Trans2 request that is bigger than its
limit, e.g. 0xffff [12]. To ensure the original buffer is received correctly
by the target machine, the exploit on the client machine sends an echo package
to the server machine. After receiving those packages, the server machine’s
buffer status changes to the one depicted in Fig. 3.

Figure 3: Server machine’s updated buffer state

Then in connection No.2, to reserve a buffer chunk which is used for grooming,
another request is sent from the client to the server. After receiving the
request, the server’s buffer status is updated as shown in Fig. 4.

Figure 4: Server machine’s updated buffer state

Next, in order to keep grooming the buffer, as in connection No.3-15 in Table.
1, multiple Srvnet requests are sent to allocate multiple Srvnet.sys buffer
chunks on the server. This is the first series of the Srvnet request packages
which fill up the slot before the second reserved buffer. Fig. 5 demonstrates
the server’s buffer status after receiving these Srvnet requests. Srvnet
connections in this step increase the probability that the Srvnet buffer
allocated in connections No.17-22 be allocated immediately following the
result list buffer because connections No.3-15 fill up the slot between the
two reserved Srv buffer (connection 2 and connection 16).

Figure 5: Server machine’s updated buffer state

As in connection No.16 in Table. 1, the second reserving buffer chunk is
reserved as a placeholder (to be replaced with the result list buffer later).
Afterwards, the first reserved buffer chunk through connection No.2 shall be
freed. The first and second buffer reserving packets also utilize a bug by
setting special parameters in the request to make the large NonPagedPool
allocation [12], which is much greater than it is permitted to. After these
two steps, the server’s buffer status changes to the one depicted in Fig. 6.

Figure 6: Server machine’s updated buffer state

Next, in connection No.17-22, extra Srvnet request packages are sent to the
server. It is expected that one Srvnet.sys buffer allocated by these requests
can be immediately after the result list buffer, hence the overflow in the
result list buffer can overwrite the following Srvnet.sys buffer’s header.
Figure. 7 shows the server buffer status after receiving the extra Srvnet
requests.

Figure 7: Server machine’s updated buffer state

In connection No.16, the second reserved buffer is freed. And in connection
No.1, the last segment of the original list is sent to the server, making the
system start the conversion.

To start the conversion process, the server tries to allocate a result list
buffer with size S1. Since the second reserved buffer, which has the size
slightly greater than the result list, is just freed, Windows memory’s last-
in-first-out working fashion guarantees this buffer be allocated as the result
list buffer. During the conversion process, as introduced before, the data in
the result buffer can overwrite the following Srvnet.sys buffer. The server
buffer status changes to the one shown in Fig. 8.

Figure 8: Server machine’s updated buffer state

Finally, the exploit sends the shellcode through each of the previously
established Srvnet connections (i.e, connection No.3-15, and 17-22).

###  2.3 Sending the shellcode

The payload is a piece of executable code that is sent after the target
machine is penetrated. Once the payload is executed, the attacker can leverage
the vulnerability and do whatever he wants to do. In previous discussion, we
have explained that by sending the grooming packages, multiple Srvnet
connections are established and one of these corresponding Srvnet.sys buffes
is expected to be overflown. According to the Check Point Reseach paper [1],
after the Srvnet connections are established, these connections wait for
another data packages and upon receiving the data packet, it will map the data
according to the parameter pMdl contained in the Srvnet buffer’s header. Also,
upon closing the Srvnet connection, the function pointed by HandlerFunction in
the pSrvnetWskStruct will be called. The Srvnet.sys buffer has a structure as
shown in Algorithm 3.

Algorithm 3 Srvnet.sys buffer structure

$Struct\ Srvnet\\_header\\{$

$......$

$MDL*pMdl1$

$......$

$Srvnet\\_receive*pSrvnetWskStruct\\{$

$......$

$PVOIDHandleFunction$

$\ \ \ \\}$

$......$

$\\}$

In this section, we have introduced the shellcode sending process. However,
the detailed code analysis on the shellcode is not discussed in this paper as
it is beyond the scope of this paper.

##  3 Code analysis

As described in Section 1, Wannacry utilizes the famous exploit Eternalblue in
its spreading process. In this section, we provide a static analysis on
Wannacry’s exploit module to investigate how this exploit is utilized. The
baseline of the analysis tools are shown below:

  * •

Wannacry SHA256 hash:
24d004a104d4d54034dbcffc2a4b19a11f39008a575aa614ea04703480b1022c

  * •

Static analysis tool: IDA 6.8

###  3.1 Wannacry

Wannacry creates local network spreading threads and Internet spreading
threads to propagate through the network. Both threads use the same exploit
Eternalblue to infect other systems.

In the local network spreading process, Wannacry creates a target IP address
table and tries to attack the potential victims in the table exhaustively. In
the Internet spreading process, Wannacry generates a random IP address and
tries to attack the system sharing the same network segment. Like Eternalblue,
the spreading process in Wannacry also consists of 3 essential steps: crafting
original list, buffer grooming and sending the payload. Table. 2 depicts the
summery of Wannacry’s package capture after we analyzed the network traffic
during the infection. This table describes almost the same process as shown in
Table. 1, except for several differences. Even though the general process
described in Table. 2 is similar to the process given in Table 1, some of the
packets are not introduced in Table. 1, as they are unique in Wannacry.

Table 2: Summery of package capture of Wannacry Step | Attempt | Packages
---|---|---
1 |  | Detect the existence of MS17_010
---
and DoublePulsar.
| PeekNamedPipe Request and Trans2 Request
---
2 |  | Send the original list except the
---
last segment.
| A NT Trans Request and multiple Trans2
---
Secondary Requests
3 |  | Ensure the package in last step
---
were sent successfully.
Echo Request
4 | Reserve the first buffer. |  | Negotiate Protocol Request and Session Setup
---
Andx Request
5 | Reserve Srvnet.sys buffers. | Multiple TCP packages
6 | Reserve the second buffer. |  | Negotiate Protocol Request and Session Setup
---
Andx Request
7 | Free the first reserved buffer. | A FIN TCP package
8 | Reserve extra Srvnet.sys buffers. | Multiple TCP packages
9 |  | Ensure the packages sent in last
---
step were sent successfully.
Echo Request
10 | Free the second reserved buffer. | A FIN TCP package
11 |  | Send the last segment of the
---
original list.
| A Trans2 Secondary Request
---
12 | Send the shellcode. | Mutiple TCP packages

Through the static analysis of Wannacry by using IDA 6.8, we discovered the
function beginning at offset 0x00401D80 crafts the fake original list and
prepares the grooming packages, which is discussed in the crafting original
list and buffer grooming steps. These fake original list, grooming packages,
and the shellcode mentioned above are embedded into the ransomworm by the
ransomworm author. During the runtime, they are extracted and pasted into a
buffer chunk in the same order as listed in Table 1. Then data in this buffer
chunk will be sent later to the server, which spreads the ransomworm and
executes the ransomworm on the server. All the data is in plain-text format
and is barely different from the Metasploit’s exploit. We will discuss the
particulars in the following paragraphs.

Prior to preparing the grooming packages and the shellcode, Wanancry sends a
PeekNamePipe package and a Trans2 Request package to detect the existence of
MS17_010 and backdoor Doublepulsar respectively [9] as in Fig. 9 and Fig. 10.
As step 1 listed in Table. 2, the PeekNamePipe package data is embedded into
the ransomworm, as depicted in Fig. 9. It is used when the ransomworm needs to
send it (by instruction call send at offset 00401AFE). After sending this
package, the ransomworm waits for the response from the server by calling the
recv function at offset 00401B15. If the data in the response package equal to
STATUS_INSUFF_SERVER_RESOURCES (0xC0000205 in hexadecimal), that denotes the
MS17_010 vulnerability resides on the server.

Figure 9: PeekNamePipe package

As shown in Fig. 10, the Trans2 package data is also embedded into the
ransomworm. The ransomworm waits for the response from the server by the
instruction call recv. If the Multiplex ID field in the response package
equals to 0x51, that denotes the server is infected with Doublepulsar, whereas
if the field equals to 0x41, that denotes the server is not infected.

Figure 10: Trans2 package

To establish the connection to the server (victim) machine, the first
Negotiate Protocol package is crafted as shown in Fig. 11. The Session Setup
AndX and Tree Connect AndX Request packages are crafted in the similar way as
depicted in Fig. 12 and Fig. 13.

Figure 11: Negotiate Protocol package Figure 12: Session Setup AndX package
Figure 13: Tree Connect AndX package

Next, as in step 2 of Table. 2, an NT Trans Request package, and multiple
Trans2 Secondary Request packages containing the crafted Os2Fea list without
the last segment are prepared as in Fig. 14, Fig. 15, and Fig. 16.

Figure 14: Nt Trans Request Figure 15: Part of Nt Trans2 Request Figure 16:
Part of Nt Trans2 Request

In step 3 of Table. 2, to ensure the original list is received completely, an
echo package is prepared as shown in Fig. 17.

Figure 17: Echo package to check original list well received

In step 4 of Table. 2, a package which reserves the first buffer chunk on the
target is prepared. The corresponding Negotiate and Session Setup Request
packages are shown in Fig. 18.

Figure 18: Grooming package reserves a buffer chunk

As in step 5 of Table. 2, to continue the buffer grooming process, multiple
Srvnet connection requests should be sent to reserve Srvnet.sys buffer chunks
on the target system. Figure. 19 shows the crafting of each Srvnet package.

Figure 19: Crafting grooming package which reserves a buffer chunk Figure 20:
Copying crafted grooming package to destination address

As in step 6 of Table. 2, the second reserving package shall be sent to the
server. The crafting process is shown in Fig. 21, including Negotiate Protocol
Request and Session Setup AndX Request. In step 7, the first reserving buffer
allocated previously shall be freed.

Figure 21: Second package to reserve a buffer chunk

In step 8, extra 5 Srvnet connection requests are crafted as shown in Fig. 22
and will be sent to the target machine to reserve Srvnet.sys buffers. It is
expected that one Srvnet.sys buffer allocated in this step is immediately
after the second reserved buffer, which will be replaced with the result list
buffer later. In step 9, an Echo package is crafted as shown in Fig. 23.

Figure 22: Crafting extra SMB2 requests which reserve Srvnet.sys buffer Figure
23: Crafting Echo request

In step 10, the second reserved buffer shall be freed and in step 11, the last
segment of the crafted original list shall be sent to the target as shown in
Fig. 24. Once this last segment is received, the target’s conversion process
(converting the original list to the result list) begins.

Figure 24: Last segment of original list

In step 12, multiple packages that contain the same shellcode are crafted as
Figs. 25. Later they will be sent through the Srvnet connections established
earlier.

Figure 25: Copying part A, B and C of the first shellcode package Figure 26:
Preparing part A, B and C of the third shellcode package Figure 27: Part A and
B of the sixth shellcode package is prepared

##  4 conclusion

The wide application of exploit Eternalblue is a meaningful security incident.
The massive infection based on Eternalblue spurs everyone to raise the
awareness of patching computers to current status. This paper introduced the
underlying mechanism of exploit Eternalblue, as well as the reverse
engineering result of Eternalblue. The code of Eternalblue applied in Wannacry
is compared with the original exploit based on the reverse engineering
results. The analysis reveals that the exploit Eternalblue is slightly
modified when applied in Wannacry. Our work gathered much-known knowledge of
Eternalblue to provide readers with a clear picture of this exploit. We have
concluded the similarity and the difference of Eternalblue’s code in Wannacry.
We have also analyzed Notpetya and found the exploit in Notpetya is encrypted
and only decrypted while the shellocode is executed. After decrypting it, the
Notepetya exploit is almost identical to the original Eternalblue exploit. Due
to the length constrains of the paper, the analysis details are not included
here. It is possible to extend our work to the code analysis for ransomworm
detection.

## References

  * [1] EternalBlue — Everything There Is To Know (2017), https://research.checkpoint.com/eternalblue-everything-know/, [Online]; accessed 15 April 2018
  * [2] Investigation: Wannacry Cyber Attack and the NHS (2018), https://www.nao.org.uk/report/investigation-wannacry-cyber-attack-and-the-nhs/, [Online]; accessed 18 March 2018
  * [3] (2019), https://msdn.microsoft.com/en-us/library/ee441928.aspx, [Online]; accessed 16 May 2018
  * [4] (2019), https://msdn.microsoft.com/en-us/library/ee441720.aspx, [Online]; accessed 16 May 2018
  * [5] (2019), https://www.dcerpc.org/documentation/rpc-porting.pdf, [Online]; accessed 18 March 2018
  * [6] Alterson, G.: Confronting One of Healthcare’s Biggest Challenges: Cyber Risk (2019), https://www.forbes.com/sites/insights-intelai/2019/02/11/confronting-one-of-healthcares-biggest-challenges-cyber-risk/amp/, [Online]; accessed 11 February 2019
  * [7] Chen, Q., Bridges, R.A.: Automated Behavioral Analysis of Malware A Case Study of Wannacry Ransomware (2017), https://arxiv.org/abs/1709.08753, [Online]; accessed 03 April 2018
  * [8] Dillon, S., Jennings, L.: ms17_010_eternalblue (2017), https://github.com/rapid7/metasploit-framework/blob/master/modules/exploits/windows/smb/ms17_010_eternalblue.rb., [Online]; accessed 24 April 2018
  * [9] KAO, D.Y., HSIAO, S.C.: The Dynamic Analysis of WannaCry Ransomware. In: International Conference on Advanced Communications Technology (ICACT) (2018), https://www.dcerpc.org/documentation/rpc-porting.pdf, [Online]; accessed 18 April 2018
  * [10] KAO, D.Y., HSIAO, S.C.: The Static Analysis of Wannacry Ransomware. In: International Conference on Advanced Communications Technology (ICACT) (2018), https://ieeexplore.ieee.org/document/8323679/, [Online]; accessed 18 April 2018
  * [11] Murakami, H.: Reverse Engineering of Wannacry Worm and Anti Exploit Snort Rules (2018), https://www.sans.org/reading-room/whitepapers/malicious/paper/38445, [Online]; accessed 07 July 2018
  * [12] Pradeep Kulkarni, Sameer Patil, P.K., Dolas, A.: Eternalblue: A prominent threat actor of 2017-2018 (2018), https://www.virusbulletin.com/uploads/pdf/magazine/2018/201806-EternalBlue.pdf, [Online]; accessed 23 May 2018
  * [13] Sanchez, W.G.: MS17-010: EternalBlue’s Large Non-Paged Pool Overflow in SRV Driver (2017), https://blog.trendmicro.com/trendlabs-security-intelligence/ms17-010-eternalblue, [Online]; accessed 16 March 2018
  * [14] sleepya: Microsoft Windows Windows 7/2008 R2 (x64) - ’Eternalblue’ SMB Remote Code Execution (MS17-010) (2017), https://www.exploit-db.com/exploits/42031/, [Online]; accessed 12 April 2018
  * [15] Thomson, I.: Leaked NSA Point-and-pwn Hack Tools Menace Win2k to Windows 8 (2017), https://www.theregister.co.uk/2017/04/14/latest_shadow_brokers_data_dump/, [Online]; accessed 5 March 2018


# Average Token Delay: A Latency Metric for Simultaneous Translation

Yasumasa Kano Katsuhito Sudoh Satoshi Nakamura
Nara Institute of Science and Technology, Japan
<EMAIL_ADDRESS>
###### Abstract

Simultaneous translation is a task in which translation begins before the
speaker has finished speaking. In its evaluation, we have to consider the
latency of the translation in addition to the quality. The latency is
preferably as small as possible for users to comprehend what the speaker says
with a small delay. Existing latency metrics focus on when the translation
starts but do not consider adequately when the translation ends. This means
such metrics do not penalize the latency caused by a long translation output,
which actually delays users’ comprehension. In this work, we propose a novel
latency evaluation metric called _Average Token Delay_ (ATD) that focuses on
the end timings of partial translations in simultaneous translation. We
discuss the advantage of ATD using simulated examples and also investigate the
differences between ATD and Average Lagging with simultaneous translation
experiments.

Average Token Delay: A Latency Metric for Simultaneous Translation

Yasumasa Kano Katsuhito Sudoh Satoshi Nakamura Nara Institute of Science and
Technology, Japan<EMAIL_ADDRESS>

##  1 Introduction

Machine translation (MT) has evolved rapidly using recent neural network
techniques and is now widely used both for written and spoken languages. MT
for speech is a very attractive application for translating various
conversations, lecture talks, etc. For smooth real-time speech communication
across languages, speech MT should run in real-time and incrementally without
waiting for the end of an input utterance as in consecutive interpretation.
While the translation quality can improve by waiting for later inputs as the
context, it should result in longer latency. This quality-latency trade-off is
the most important issue in simultaneous MT.

Most recent simultaneous MT studies use BLEU (Papineni et al., 2002) for
evaluating the quality and Average Lagging (AL; Ma et al., 2019) for the
latency. AL is based on the number of input words that have become available
when starting a translation and measures its average over all the timings of
generating partial translations. It is very suitable for wait-$k$ (Ma et al.,
2019) that waits for $k$ input tokens before starting the translation and then
repeats to read and write one token alternately.

Figure 1: wait-3 and chunk-3 in a step-wise view.

Figure 2: wait-3 and chunk-3 in a time-synchronous view.

This work focuses on a problem of AL. AL does not sufficiently consider the
cases where chunk-level outputs are generated at a time and give smaller
latency values for them than one-by-one cases like wait-$k$.

Suppose we have a pair of seven input tokens and seven output tokens and apply
two different simultaneous policies to this pair as shown in Figure 2:
wait-$3$ and _chunk-3_ that writes three tokens after reading three tokens.
Figure 2 illustrates a situation where one input or output token requires one
unit time to speak, ignoring computation time for simplicity. These policies
are equivalent to each other, from the viewpoint of latency in this situation.
However, AL for wait-$3$ is $\frac{15}{5}=3$ and that for chunk-$3$ is
$\frac{13}{7}\approx 1.857$. AL tends to give a small latency value for such a
long chunk-level output. However, a long output delays the start of the
translation of later parts and makes the listener feel the delay. This problem
becomes more severe when we need speech outputs because the speech outputs
must be sequential. Therefore, the length of a translation output has a large
effect on delay and should be included in the latency measurement. This
observation suggests the need of another latency metric to cope with such
situations.

In this paper, we propose a novel latency metric called _Average Token Delay_
(ATD) 111ATD will be implemented in
https://github.com/facebookresearch/SimulEval that focuses on the end timings
of partial translations. ATD generalizes the latency measurement for
simultaneous translation both with speech and text outputs and works
intuitively for chunk-based outputs that are not properly handled by AL as
presented above. We present some simulation results to show the
characteristics of ATD clearly and also demonstrate its effectiveness through
simultaneous translation experiments.

##  2 Simultaneous Machine Translation

We quickly review the formulation of simultaneous translation to share the
notation used in this paper.

In standard sentence-level NMT, letting $\bm{x}=x_{1},x_{2},...,x_{m}$ be an
input sentence and $\bm{y}=y_{1},y_{2},...,y_{n}$ be its translation, the
probability of the output is denoted as:

$p(\bm{y}|\bm{x})=\prod_{\tau=1}^{n}P(y_{\tau}|\bm{x},\bm{y}_{<\tau}).$ (1)

Simultaneous translation takes a prefix of the input for its incremental
decoding, formulated as follows:

$p(\bm{y}|\bm{x})=\prod_{\tau=1}^{n}P(y_{\tau}|\bm{x}_{\leq
g(\tau)},\bm{y}_{<\tau}),$ (2)

where $g(\tau)$ is a monotonic non-decreasing function that represents the
number of input tokens read until the prediction of $\tau$-th output so that
$\bm{x}_{\leq g(\tau)}$ means an input prefix, and $\bm{y}_{<\tau}$ is a
prefix translation predicted so far. This means that we can obtain a pair of a
input prefix and the corresponding prefix translation $(\bm{x}_{\leq
g(\tau)},\bm{y}_{\leq\tau})$ by that time.

The incremental decoding can be represented by a sequence of actions, READ and
WRITE. READ is the action to take a new input, typically one token for text
input or fixed number of frames for speech input. WRITE is the action to
predict an output, typically one token for text output or the corresponding
speech signal for speech output. In this paper, we use $t$ ($0\leq
t\leq|\bm{x}|+|\bm{y}|$) for an index in such an action sequence and $\tau$
($0\leq\tau\leq|\bm{y}|$) for an index in the output.

##  3 Existing Latency Metrics for Simultaneous Translation

###  3.1 Consecutive Wait (CW)

Gu et al. (2017) proposed a latency metric called Consecutive Wait (CW) to
measure the local delay. CW at the step $t$ is denoted as follows:

$\mathrm{CW}(t)=\begin{cases}\mathrm{CW}(t-1)+1&a_{t}=\text{ {READ} }\\\
0&a_{t}=\text{ {WRITE} }\end{cases}$

where $\mathrm{CW}(0)=0$, $a_{t}$ means an action at the step $t$.

Since CW is not originally an average measure of the latency, Ma et al. (2019)
used a step-wise CW: $\mathrm{CW}_{g}(\tau)=g(\tau)-g(\tau-1)$ for a policy
$g(\cdot)$ to calculate an average CW for a sentence pair $(\bm{x},\bm{y})$ as
follows:

$\mathrm{CW}_{g}(\bm{x},\bm{y})=\frac{\sum_{\tau=1}^{|\bm{y}|}\mathrm{CW}_{g}(\tau)}{\sum_{\tau=1}^{|\bm{y}|}\mathbbm{1}_{\mathrm{CW}_{g}(\tau)>0}}=\frac{|\bm{x}|}{\sum_{\tau=1}^{|\bm{y}|}\mathbbm{1}_{\mathrm{CW}_{g}(\tau)>0}}$
(3)

$g(\tau)$ is a monotonic non-decreasing function which represents number of
source words read to predict the $\tau$-th target word. This average CW
becomes larger when WRITE actions happen consecutively because
$\mathrm{CW}_{g}(\tau)=0$ when $g(\tau)-g(\tau-1)=0$, i.e., the $\tau$-th and
$(\tau-1)$-th output tokens are generated in the consecutive steps. It is not
intuitively appropriate to measure the latency of a sentence pair. The average
CW result in the same value for the following two extreme cases: (1) all the
output tokens are generated after reading all input tokens
($a_{1}=...=a_{|\bm{x}|}=\text{{READ}}$,
$a_{|\bm{x}|+1}=...=a_{|\bm{x}|+|\bm{y}|}=\text{{WRITE}}$) and (2) all the
output tokens are generated after reading only the first input token
($a_{1}=\text{{READ}}$, $a_{2}=...=a_{|\bm{y}|+1}=\text{{WRITE}}$,
$a_{|\bm{y}|+2}=...=a_{|\bm{x}|+|\bm{y}|}=\text{{READ}}$).

###  3.2 Average Propotion (AP)

Cho and Esipova (2016) proposed Average Proportion (AP). AP for a sentence
pair $(\bm{x},\bm{y})$ is denoted as follows:

$\mathrm{AP}_{g}(\bm{x},\bm{y})=\frac{1}{|\bm{x}||\bm{y}|}\sum_{\tau}g(\tau)$
(4)

Suppose we use the wait-1 policy. The sum $\sum_{\tau}g(\tau)$ is given by
$\sum_{\tau=1}^{|\bm{y}|}\tau$. For a sentence pair with
$|\bm{x}_{1}|=|\bm{y}_{1}|=1$, $\mathrm{AP}(\bm{x}_{1},\bm{y}_{1})=1$. When
the length becomes longer, e.g., $|\bm{x}_{10}|=|\bm{y}_{10}|=10$,
$\mathrm{AP}(\bm{x}_{1},\bm{y}_{1})=0.55$. AP differs with the change of the
sequence length for the same simultaneous translation policy and is not
intuitive for the latency metric.

###  3.3 Average Lagging (AL)

Ma et al. (2019) proposed Average Lagging (AL). AL is denoted as follows:

$AL_{g}(\bm{x},\bm{y})=\frac{1}{\tau_{g}(|\bm{x}|)}\sum_{\tau=1}^{\tau_{g}(|\bm{x}|)}\left(g(\tau)-\frac{\tau-1}{r}\right).$
(5)

where r is the length ratio defined as $|\bm{y}|/|\bm{x}|$ and
$\tau_{g}(|\bm{x}|)$ is the cut-off step defined as follows:

$\tau_{g}(|\bm{x}|)=\min\\{\tau\mid g(\tau)=|\bm{x}|\\}$ (6)

meaning the index of the output token predicted right after the observation of
the entire source sentence.

AL solves the problem of AP mentioned above by focusing on the difference from
the _ideal_ policy based on the length ratio. However, AL still suffers from
unintuitive latency measurement because AL can be negative when the model
finishes the translation before reading the entire input due to the
subtraction term. Ma et al. (2020) modified AL by changing the calculation of
the length ratio $r$ based on the length of the reference translation. Papi et
al. (2022) proposed Length-Adaptive Average Lagging (LAAL) that uses the
longer one between the reference and output. These modifications do not
completely avoid negative values when the model generates a long partial
output faster than the ideal policy. Arivazhagan et al. (2019) proposed
another variant, Differentiable Average Lagging (DAL), for optimizing
simultaneous translation model. Iranzo-Sánchez et al. (2021) proposed a method
to calculate AL for a streaming input in a segmentation-free manner.

##  4 Proposed Metric: Average Token Delay

We propose a novel latency metric called Average Token Delay (ATD). We start
from the latency measurement using ATD in case of simultaneous speech-to-
speech MT and then generalize it for speech-to-text and text-to-text cases.

Figure 3: Step-by-step example of simultaneous speech-to-speech MT

###  4.1 ATD for simultaneous speech-to-speech translation

Figure 3 illustrates a step-by-step workflow of simultaneous speech-to-speech
MT. In this figure, the white boxes represent fixed-length speech segments,
the orange ones represent the processing time to encode prefix inputs and to
judge whether prefix translations can be predicted there, and the blue ones
represent decoding time. Intuitively, ATD is the average time difference
between the points of the same color (black, red, and white).

Suppose we have an input $\bm{x}$ and an output $\bm{y}$ segmented into $C$
chunks $\bm{x}=\bm{x}^{1},\bm{x}^{2},...,\bm{x}^{C}$ and
$\bm{y}=\bm{y}^{1},\bm{y}^{2},...,\bm{y}^{C}$, respectively. An input chunk
$\bm{x}^{c}$ is what is observed after the previous judgment for the prefix
translation $\bm{y}^{c-1}$ and is used to predict $\bm{y}^{c}$. In the case of
text, each chunk consists of sub-segments with words, subwords, or characters.
In the case of speech, we divide each chunk into sub-segments of 0.3 seconds
long from the beginning of the chunk, assuming one word is uttered in 0.3
seconds. Through this segmentation, the input and output sentences can be
represented as a series of sub-segments $\bm{x}=x_{1},...,x_{|\bm{x}|}$,
$\bm{y}=y_{1},...,y_{|\bm{y}|}$ respectively.

ATD is defined as follows:

$\textrm{ATD}(\bm{x},\bm{y})=\frac{1}{|\bm{y}|}\sum_{t=1}^{|\bm{y}|}\left(T(y_{t})-T(x_{a(t)})\right)$
(7)

where

$a(t)=\begin{cases}s(t)&\textrm{if}\ s(t)\leq L_{acc}(\bm{x}^{c(t)})\\\
L_{acc}(\bm{x}^{c(t)})&\textrm{otherwise}\end{cases}$ (8)
$s(t)=t-\max(L_{acc}(\bm{y}^{c(t)-1})-L_{acc}(\bm{x}^{c(t)-1}),0)$ (9)

$T(\cdot)$ in Eq. (7) represents the ending time of each token, which is shown
as colored points in Figure 3. $a(t)$ represents the index of the input token
corresponding to $y_{t}$. $L_{acc}(\bm{x}^{c})=\sum_{j=1}^{c}|\bm{x}^{j}|$ is
the cumulative length up to the $c$-th chunk, and $L_{acc}(\bm{x}^{0})=0$.
$L_{acc}(\bm{y}^{c})$ is defined similarly. $c(t)$ denotes the chunk number
$c$ to which $y_{t}$ belongs. As shown in Eq. (9), if the previous translation
prefix is longer than the previous input prefix, $s(t)$ becomes smaller than
the output index $t$, which means the previous long output makes the time
difference between the input token and the corresponding output token larger.

ATD is the average delay of output sub-segments against their corresponding
input sub-segments, considering the latency required for inputs and outputs.
Although the input-output correspondence does not necessarily mean semantic
equivalence, especially for language pairs with large differences in their
word order and the numbers of tokens, we use this simplified formulation for
the latency measurement as same as AL.

$\leftarrow L_{acc}(\bm{x}^{1})\rightarrow$ |  |  |  |  |
---|---|---|---|---|---
$\bm{x}^{1}$ | $\bm{x}^{2}$ |  |  |
$x_{1}$ | $x_{2}$ | $x_{3}$ | $x_{4}$ | $x_{5}$ |  |  |
|  |  | $y_{1}$ | $y_{2}$ | $y_{3}$ | $y_{4}$ | $y_{5}$
|  |  | $\bm{y}^{1}$ | $\bm{y}^{2}$
|  |  | $\leftarrow L_{acc}(\bm{y}^{1})\rightarrow$ |  |
(a) $L_{acc}(\bm{y}^{c(t)-1})-L_{acc}(\bm{x}^{c(t)-1})=0$ ($t=5$)

$\leftarrow L_{acc}(\bm{x}^{1})\rightarrow$ |  |  |  |  |  |
---|---|---|---|---|---|---
$\bm{x}^{1}$ | $\bm{x}^{2}$ |  |  |  |
$x_{1}$ | $x_{2}$ | $x_{3}$ | $x_{4}$ | $x_{5}$ |  |  |  |
|  |  | $y_{1}$ |  | $y_{2}$ | $y_{3}$ | $y_{4}$ | $y_{5}$
|  |  | $\bm{y}^{1}$ |  | $\bm{y}^{2}$
|  | $\rightarrow$ |  | $\leftarrow L_{acc}(\bm{y}^{1})$ |
(b) $L_{acc}(\bm{y}^{c(t)-1})-L_{acc}(\bm{x}^{c(t)-1})<0$ ($t=2$)

$\leftarrow L_{acc}(\bm{x}^{1})\rightarrow$ |  |  |  |  |  |
---|---|---|---|---|---|---
$\bm{x}^{1}$ | $\bm{x}^{2}$ |  |  |  |
$x_{1}$ | $x_{2}$ | $x_{3}$ | $x_{4}$ | $x_{5}$ |  |  |  |
|  |  | $y_{1}$ | $y_{2}$ | $y_{3}$ | $y_{4}$ | $y_{5}$ | $y_{6}$
|  |  | $\bm{y}^{1}$ | $\bm{y}^{2}$
|  |  | $\longleftarrow\hskip 5.69054ptL_{acc}(\bm{y}^{1})\hskip 5.69054pt\longrightarrow$ |  |
(c) $L_{acc}(\bm{y}^{c(t)-1})-L_{acc}(\bm{x}^{c(t)-1})>0$ ($t=5$)

Figure 4: Examples for the explanation of Eq. (9)

$\leftarrow L_{acc}(\bm{x}^{1})\rightarrow$ |  |  |
---|---|---|---
$\bm{x}^{1}$ |  |  |
$x_{1}$ | $x_{2}$ | $x_{3}$ |  |  |
|  |  | $y_{1}$ | $y_{2}$ | $y_{3}$
|  |  | $\bm{y}^{1}$
|  |  | $\leftarrow L_{acc}(\bm{y}^{1})\rightarrow$
(a) $s(t)\leq L_{acc}(\bm{y}^{c(t)})$ ($t=3$)

$\leftarrow L_{acc}(\bm{x}^{1})\rightarrow$ |  |  |  |
---|---|---|---|---
$\bm{x}^{1}$ |  |  |  |
$x_{1}$ | $x_{2}$ | $x_{3}$ |  |  |  |
|  |  | $y_{1}$ | $y_{2}$ | $y_{3}$ | $y_{4}$
|  |  | $\bm{y}^{1}$
|  |  | $\longleftarrow\hskip 5.69054ptL_{acc}(\bm{y}^{1})\hskip 5.69054pt\longrightarrow$
(b) $s(t)>L_{acc}(\bm{y}^{c(t)})$ ($t=4$)

Figure 5: Example for the explanation of Eq. (8)

Figure 4 shows examples to explain the term in $\max$ operator in Eq. (9). In
Figure 4, Suppose we measure the token delay on $y_{5}$. $\bm{y}_{5}$ is in
the second output chunk, so $c(5)=2$. Since
$L_{acc}(\bm{y}^{1})=L_{acc}(\bm{x}^{1})=3$, we obtain $a(5)=s(5)=5-0=5\leq
L_{acc}(\bm{x}^{2})=5$, and therefore $\bm{y}_{5}$ corresponds to
$\bm{x}_{5}$. In Figure 4, Suppose we measure the token delay on $y_{2}$.
$y_{2}$ is in the second output chunk, so c(2) = 2. Since
$L_{acc}(\bm{y}^{1})-L_{acc}(\bm{x}^{1})=1-3<0$, we obtain
$a(2)=s(2)=2-0=2\leq L_{acc}(x^{2})=5$, therefore $y_{2}$ corresponds to
$x_{2}$. In Figure 4, the first output chunk is longer:
$L_{acc}(\bm{y}^{1})=4$. This results in $a(5)=s(5)=5-1=4\leq
L_{acc}(\bm{x}^{2})=5$, so $\bm{y}_{5}$ corresponds to $\bm{x}_{4}$.

Figure 5 shows examples to explain Eq. (8). In Figure 5, we measure the token
delay on $y_{3}$. Here, we obtain $s(t)=3\leq L_{acc}(\bm{x}^{1})=3$, so
$y_{3}$ corresponds to $x_{3}$. Figure 5, we measure the token delay on
$y_{4}$. Here, we obtain $s(t)=4>L_{acc}(\bm{x}^{1})=3$, so $y_{4}$
corresponds to $x_{3}$.

Figure 6: Summary view for latency measurement for simultaneous speech-to-text
translation

Figure 7: Summary view for latency measurement for simultaneous text-to-text
translation

Figure 8: Summary view for non-computation-aware latency measurement for
simultaneous text-to-text translation

###  4.2 ATD for simultaneous {speech,text}-to-text translation

Figure 8 illustrates the latency measurement for speech-to-text simultaneous
translation, where the output duration can be ignored. Figure 8 is the one for
text-to-text simultaneous translation. We reserve input duration here because
input for text-to-text simultaneous translation comes from speech via
automatic speech recognition (ASR), in most cases. The input duration reflects
ASR computation time.

###  4.3 Non-computation-aware ATD

We sometimes use the latency measurement independent of the computation time
for estimating ideal situations that are not influenced by the performance of
computers and the efficiency of implementations. In Figures 3, 8, and 8, we
remove the orange, blue and yellow parts and only include the duration of
speech segments to calculate delay. However, this means all the terms in text-
to-text translation become 0. We follow the conventional step-wise latency
measurement as CW and AP by letting each input and output word spend one step
as shown in Figure 8. Also, we assume the model can read the next input and
output the partial translation in parallel as shown in Figure 2.

##  5 Simulation

Before presenting the latency measurement experiments using real data, we show
simulation results comparing AL and ATD in different conditions in
simultaneous text-to-text translation.

###  5.1 Case 1: 40-40

(a) Latency measurement by AL (40-40)

(b) Latency measurement by ATD (40-40)

Figure 9: Case 1 (40 input and 40 output tokens)

We assume that the numbers of tokens of the input and output are both 40. We
compare the latency measurement by AL and ATD where the hyperparameter $k$ for
wait-$k$ and chunk-$k$ varies from 1 to 40. Here, for simplicity, we assume
the length of input and output chunks are the same for chunk-$k$ until the
prediction of the end-of-sentence token.

Figure 9 shows the results. Figure 9 indicates the gap between wait-$k$ and
chunk-$k$ by AL mentioned in section 1, while ATD results in the same values
for them as shown in Figure 9. One serious problem raised here is the large
jump in AL at $k=40$. For example, in the case of chunk-$39$, AL uses $r=1$,
$\tau_{g_{\textrm{chunk-}39}}(|\bm{x}|)=40$, $g_{\textrm{chunk-}39}(\tau)=39$
($1\leq\tau\leq 39$), and $g_{\textrm{chunk-}39}(\tau)=40$ ($\tau=40$). Then
the AL value becomes
$\frac{1}{40}\left\\{\left(\sum_{\tau=1}^{39}\tau\right)+1\right\\}=\frac{781}{40}=19.525$.
However, in the case of chunk-$40$, $g_{\textrm{chunk-}40}(\tau)=40$ for all
$\tau$ and $\tau_{g_{\textrm{chunk-}40}}(|\bm{x}|)=1$ according to Equation 6.
As a result, the AL value becomes 40. This phenomenon comes from the
definition of the cut-off step described in Section 4.2 by Ma et al. (2019),
where they assume later outputs derive no further delays.

###  5.2 Case 2: 40-100

(a) Latency measurement by AL (40-100)

(b) Latency measurement by ATD (40-100)

Figure 10: Case 2 (40 input and 100 output tokens)

Next, we simulate another situation with an input of 40 tokens and an output
of 100 tokens and conduct the same analysis. Figure 10 shows the results. As
shown in Figure 10, AL suffers from discontinuous latency values for chunk-$k$
that are caused by similar phenomena in the example above. In contrast, ATD
results in the same linear correlations for wait-$k$ and chunk-$k$ as shown in
Figure 10.

###  5.3 Case 3: 40-20

(a) Latency measurement by AL (40-20)

(b) Latency measurement by ATD (40-20)

Figure 11: Case 3 (40 input and 20 output tokens)

We also tried a situation with a shorter output of 20 tokens, keeping the
input of 40 tokens. Figure 11 shows the results. An important finding from
Figure 11 is that AL gives negative values both for wait-$k$ and chunk-$k$
with small values of $k$. AL also suffers from non-smooth changes in latency
values even though they are almost continuous unlike Figure 10. ATD results in
stable latency measurement both for wait-$k$ and chunk-$k$ in this situation,
as shown in Figure 11.

###  5.4 Case 4: (20+20)-($L_{1}$+20)

Figure 12: Case 4 (20+20 input and $L_{1}$+20 output tokens with varying
$L_{1}$)

We conduct another type of simulation by dividing an input into two parts and
varying the length of the output corresponding to the first input part. Here,
we assume the input is divided into two segments with 20 tokens each and the
corresponding outputs are with $L_{1}$ and 20 tokens each with varying
$L_{1}$. Figure 12 shows the results using a chunk-$20$ strategy.

If $L_{1}<20$, some target tokens corresponding to the first input chunk come
after reading the second chunk. Figure 4 shows such situation, in which
$L_{1}=L_{acc}(y^{1})=1<2$. If $y_{2}$ is in the first chunk output and
$L_{1}=L_{acc}(y^{1})=2$, the time difference between $x_{2}$ and $y_{2}$
becomes smaller. It also makes the time difference of the latter token pairs
such as $x_{3}$ and $y_{3}$ smaller. Therefore, the shorter $L_{1}$ becomes,
the larger the delay becomes in this range.

If $L_{1}>20$, the translation of the second chunk is delayed due to the long
translation outputs for the first chunk as described in Figure 4. Therefore,
the longer $L_{1}$ becomes, the larger the delay becomes in this range. ATD
reflects this phenomena while AL decreases monotonically with $L_{1}$.

###  5.5 Case 5: (20+20)-(20+$L_{2}$)

Figure 13: Case 5 (20+20 input and 20+$L_{2}$ output tokens with varying
$L_{2}$)

Then, we analyze a similar situation varying the length of the second output
part $L_{2}$. Our assumption here is: the input is the same two 20-token
segments, and the output consists of the first 20-token segment and the second
$L_{2}$ token segment. Figure 13 shows the results using a chunk-$20$
strategy. Although both AL and ATD values increase with larger $L_{2}$, AL
shows very small values close to zero even though we have to wait for 20
tokens in the first output part; this is not intuitive as the latency metric.
In contrast, ATD shows a gradual increase in latency values similar to Figure
12 due to additional delays by longer outputs.

###  5.6 Case 6: Translation example

Figure 14: Case 6

Figure 14 shows examples of chunk-based simultaneous translation for the input
_I bought a pen._ by three different models.

Model 1 waits for the whole input sentence and results in the largest delay
and the highest translation quality.

Model 2 has a smaller delay than Model 1 because it can segment the input
after observing _I_. The segmentation enables the model to generate a partial
translation but causes quality degradation due to the lack of context.

Model 3 works similarly to Model 2 for the input segmentation but outputs a
longer segment for _I_. This causes large quality degradation by over-
translation.

Regarding the latency of these three models, AL is the smallest for Model 3
and decreases largely from Model 1 to Model 2; they are not intuitive as
discussed so far. In contrast, ATD results in reasonable latency values
considering the delay caused by the outputs.

##  6 Analyses

We conducted analyses on actual simultaneous translation results to
investigate the effectiveness of ATD. We chose the language directions of
English-to-German (en-de) and English-to-Japanese (en-ja) for the comparison
of AL and ATD in different conditions in terms of word order. Note that the
analyses here were conducted on simultaneous text-to-text translation for
simplicity.

###  6.1 Data

We used the data from the IWSLT evaluation campaign. For English-to-Geman, we
used WMT 2014 training set (4.5 M sentence pairs) for pre-training and IWSLT
2017 training set (206 K sentence pairs) for fine-tuning. The development set
consists of dev2010, tst2010, tst2011 and tst2012 (5,589 sentence pairs in
total), and the evaluation set is tst2015 (1,080 sentence pairs). For English-
to-Japanese, we used WMT 2020 training set (17.9 M sentence pairs) for pre-
training and IWSLT 2017 (223 K sentence pairs) for fine-tuning. The
development set consists of dev2010, tst2011, tst2012, and tst2013 (5,312
sentence pairs in total), and the evaluation set is dev2021 (1,442 sentence
pairs).

We compared wait-$k$ (Ma et al., 2019), Meaningful Unit (MU; Zhang et al.,
2020), Incremental Constitute Label Prediction (ICLP; Kano et al., 2021), and
Prefix Alignment (PA; Kano et al., 2022), following the the experimental
settings in the literature (Kano et al., 2022).

###  6.2 Results

####  6.2.1 English-to-German

(a) Latency measurement by AL (en-de)

(b) Latency measurement by ATD (en-de)

Figure 15: English-to-German

Figure 16: Length ratio and AL (en-de)

Figure 16 shows the results in English-to-German. Compared to AL shown in
Figure 16, ATD shown in Figure 16 demonstrated clear differences in delay
among models. MU and ICLP were affected by the change in the latency metric.
We analyzed their results in detail and found this degradation was due to
over-translation as suggested by the observations of length ratio results
shown in Figure 16. This phenomenon is the same as what happened with Model 3
in subsection 5.6. MU and ICLP generated long translations exceeding the
length ratio of 1.0 when they worked with small latency. One interesting
finding here is the correlation between BLEU and ATD by MU; larger latency did
not always result in better BLEU. It is because over-translation increases
ATD, but decreases BLEU at the same time. In contrast, wait-$k$ is a strategy
that generates one output token at a time and can avoid such an issue. PA also
worked well with the latency measurement by ATD because it fine-tunes the
translation model to avoid over-translation.

####  6.2.2 English-to-Japanese

(a) Latency measurement by AL (en-ja)

(b) Latency measurement by ATD (en-ja)

Figure 17: English-to-Japanese

Figure 17 shows the results in English-to-Japanese. The results were similar,
but the actual latency values of ATD were much larger than those in English-
to-German. This is also due to the limitation of the current implementation of
ATD based on SimulEval Ma et al. (2020), where the latency in text-to-text
English-to-Japanese translation is calculated based on the number of Japanese
characters, not the number of words as in English-to-German. Therefore, the
number of output tokens had to be much larger than the number of input tokens
in English-Japanese, so the ATD value became large. This large number of
output tokens made the effect of over-translation by MU in Figure 17 more
serious than that in English-to-German.

##  7 Conclusion

We proposed a novel latency metric ATD for simultaneous machine translation,
which addresses the problem in the latency evaluation for a chunk-based model
by taking the output length into account. ATD gives a large latency value to a
long output based on the assumption that the output also causes a delay,
different from AL. We revealed the effectiveness of ATD through the analyses
of simulation and actual translation results compared with AL.

Future work includes studies on semantics-oriented latency measurement not
just focusing on timing information without any consideration about the
delivery of contents.

## Acknowledgements

Part of this work is supported by JSPS KAKENHI Grant Number JP21H05054.

## References

  * Arivazhagan et al. (2019) Naveen Arivazhagan, Colin Cherry, Wolfgang Macherey, Chung-Cheng Chiu, Semih Yavuz, Ruoming Pang, Wei Li, and Colin Raffel. 2019.  Monotonic infinite lookback attention for simultaneous machine translation.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 1313–1323, Florence, Italy. Association for Computational Linguistics.
  * Cho and Esipova (2016) Kyunghyun Cho and Masha Esipova. 2016.  Can neural machine translation do simultaneous translation?  _arXiv preprint arXiv:1606.02012._
  * Gu et al. (2017) Jiatao Gu, Graham Neubig, Kyunghyun Cho, and Victor O.K. Li. 2017.  Learning to translate in real-time with neural machine translation.  In _Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers_ , pages 1053–1062, Valencia, Spain. Association for Computational Linguistics.
  * Iranzo-Sánchez et al. (2021) Javier Iranzo-Sánchez, Jorge Civera Saiz, and Alfons Juan. 2021.  Stream-level latency evaluation for simultaneous machine translation.  In _Findings of the Association for Computational Linguistics: EMNLP 2021_ , pages 664–670, Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Kano et al. (2021) Yasumasa Kano, Katsuhito Sudoh, and Satoshi Nakamura. 2021.  Simultaneous neural machine translation with constituent label prediction.  In _Proceedings of the Sixth Conference on Machine Translation_ , pages 1124–1134, Online. Association for Computational Linguistics.
  * Kano et al. (2022) Yasumasa Kano, Katsuhito Sudoh, and Satoshi Nakamura. 2022.  Simultaneous neural machine translation with prefix alignment.  In _Proceedings of the 19th International Conference on Spoken Language Translation (IWSLT 2022)_ , pages 22–31, Dublin, Ireland (in-person and online). Association for Computational Linguistics.
  * Ma et al. (2019) Mingbo Ma, Liang Huang, Hao Xiong, Renjie Zheng, Kaibo Liu, Baigong Zheng, Chuanqiang Zhang, Zhongjun He, Hairong Liu, Xing Li, Hua Wu, and Haifeng Wang. 2019.  STACL: Simultaneous translation with implicit anticipation and controllable latency using prefix-to-prefix framework.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 3025–3036, Florence, Italy. Association for Computational Linguistics.
  * Ma et al. (2020) Xutai Ma, Mohammad Javad Dousti, Changhan Wang, Jiatao Gu, and Juan Pino. 2020.  SIMULEVAL: An evaluation toolkit for simultaneous translation.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 144–150, Online. Association for Computational Linguistics.
  * Papi et al. (2022) Sara Papi, Marco Gaido, Matteo Negri, and Marco Turchi. 2022.  Over-generation cannot be rewarded: Length-adaptive average lagging for simultaneous speech translation.  In _Proceedings of the Third Workshop on Automatic Simultaneous Translation_ , pages 12–17, Online. Association for Computational Linguistics.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  Bleu: a method for automatic evaluation of machine translation.  In _Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics_ , pages 311–318, Philadelphia, Pennsylvania, USA. Association for Computational Linguistics.
  * Zhang et al. (2020) Ruiqing Zhang, Chuanqiang Zhang, Zhongjun He, Hua Wu, and Haifeng Wang. 2020.  Learning adaptive segmentation policy for simultaneous translation.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 2280–2289, Online. Association for Computational Linguistics.


11institutetext: University of Pisa, Italy,
11email: {g.pisciotta1, m.somenzi<EMAIL_ADDRESS>22institutetext: KDD Lab, ISTI-CNR, Italy
22email<EMAIL_ADDRESS>
# Sockpuppet Detection: a Telegram case study

Gabriele Pisciotta 11 Miriana Somenzi 11 Elisa Barisani 11 Giulio Rossetti 44

##  1 Introduction

In Online Social Networks (OSN) numerous are the cases in which users create
multiple accounts that publicly seem to belong to different people but are
actually fake identities of the same person. These fictitious characters can
be exploited to carry out abusive behaviors such as manipulating opinions,
spreading fake news and disturbing other users [4, 2]. In literature this
problem is known as the ”Sockpuppet problem”.
In our work we focus on Telegram, a wide-spread instant messaging application,
often known for its exploitation by members of organized crime and terrorism,
and more in general for its high presence of people who have offensive
behaviors. In Italy, for example, it stepped into the spotlight because of a
revenge porn case in early 2020. In this OSN users can chat both privately and
in groups, and its peculiarity is that they can interact anonymously, because
the service allows you to display only your nickname of choice, keeping any
other personal information hidden. This feature facilitates the emergence of
various fake accounts, exploiting also free VoIP numbers to create a variety
of sockpuppet accounts.
The detection of sockpuppet accounts is a challenging task and the
approaches[5] that have been tried during these years involve many different
platforms and OSN; furthermore these techniques can be tailored or applied in
a more general way. The majority of them often relies on the use of Natural
Language Processing (NLP) methods, OSN-dependent features and mined behavioral
patterns.
Thus we decided to tackle the problem in an innovative way to try and have
more interesting results, that is by involving Network Science as a tool to
match different virtual users that are actually the same person offline. To do
so we took several Italian public groups on Telegram, choosing them because of
the similarity in their academic contents and the fact that these groups have
some users in common (they actually belong to the same virtual network of
self-declared ”friends group”). We scraped these groups’ messages and
exploited the replies between users, all this in a completely undetectable way
from the inside thanks to the fact that it is not necessary to join the groups
to retrieve the informations.
We then created a directed weighted network of user interactions that connects
the users who write a message, the source, to the users to whom they reply,
the target. We took 17747 users as nodes and 191526 explicit replies to
messages as edges, weighted by the number of replies.

##  2 Preliminar Results

We decided to investigate the power of Network Science applied on Sockpuppet
Detection in Telegram. More in depth, we saw this problem as an instance of
the link prediction task based on similarity measures, where the link has the
meaning of ”same-as”. In agreement to this the whole problem can be seen as an
instance of the data linking problem that, according to the particular
scenario taken into account, can be named as deduplication (w.r.t. databases),
instance matching (w.r.t knowledge graphs) and entity resolution: we decided
to to treat it in a similar way, trying to find cluster of similar instances.
We propose a scalable method that exploits neighbours as features. In order to
assess the similarity between the nodes we should compute the similarity
matrix according to a certain function and filter that need to be the closest
possible to a given threshold. However this operation is very costly, both in
memory and time, being O($n^{2}$) (where n is the number of nodes). To tackle
this scalability issue we involved a family of algorithms known as Locality-
Sensitive Hashing (LSH)[1] that create blocks in which similar entities are
stored based on an hash function that takes each entity’s feature as input:
similar entities should lead to similar hash, so they should belong to the
same cluster. Instead of computing the similarity between each pair of nodes,
using LSH algorithms we drop from a complexity of O($n^{2}$) to O(n), allowing
us to scale w.r.t the number of nodes. In specific we use SimHash [3], to
approximate the hamming distance between the the nodes and get the clusters.
Before computing the similarity between nodes, we preprocessed the data in
this way:

  * •

we normalized neighbours’ weight according to each user

  * •

we dropped links having weight less than 0.5 to only take into account the
more meaningful interactions

For each node we wanted to limit the number of similar ones to have few
candidates: to do this, we set the fingerprint size to 128 and the max
distance to 20.

Using a real life scraped dataset we were not able to create a full ground
truth; moreover we only had a partial knowledge of all the users in it.
Considering this, we acted as an oracle and we tested our method on a small
number of users that we knew for sure being accounts of the same person.
With only this topological information (up to now we had just used the
neighbours similarity) we have found both bidirectional exact match and one-
to-many matches. For the last case, we found also users that are not related,
based on our knowledge. Varying the value of the signature size and the max
distance, we’re able to both find new correct match and to lose them. We
suggest to find a trade-off between these values, according to the precision
and the recall metrics.
Unfortunately the downside we encountered using this feature was the discovery
of a lot of false positives belonging to people that we know to be different
from the main sockpuppet account we were looking for.

Network Science can provide a very effective framework to tackle the search of
sockpuppet accounts in OSN, and it can be an interesting research direction
because of the possibility of exploiting the structure of interactions that
emerges with time. Furthermore this is something that is not OSN-dependent
making it possible to hypothetically create an interaction graph from every
OSN.
As future works we also plan to extend the experimentation involving labeled
datasets and trying to combine other features mined from the graph. We have
also started to explore the usage of lexical features that can be extracted
from sent messages, using them in combination with the previously described
ones, in order to investigate the influence of structural informations and
linguistic ones. The first results are really promising and we are continuing
to improve our research on the subject.

## Acknowledgements

This work is supported by the scheme ’INFRAIA-01-2018-2019: Research and
Innovation action’, Grant Agreement n. 871042 ’SoBigData++: European
Integrated Infrastructure for Social Mining and Big Data Analytics’.

## References

  * [1] Indyk, P., Motwani, R.:  Approximate nearest neighbors: Towards removing the curse of dimensionality.  In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing. STOC ’98, New York, NY, USA, Association for Computing Machinery (1998) 604–613
  * [2] Li, J., Yuan, C., Zhou, W., Wang, J., Hu, S.:  Who are controlled by the same user? multiple identities deception detection via social interaction activity (student abstract).  Proceedings of the AAAI Conference on Artificial Intelligence 34(10) (apr 2020) 13853–13854
  * [3] Manku, G.S., Jain, A., Das Sarma, A.:  Detecting near-duplicates for web crawling.  In: Proceedings of the 16th International Conference on World Wide Web. WWW ’07, New York, NY, USA, Association for Computing Machinery (2007) 141–150
  * [4] Solorio, T., Hasan, R., Mizan, M.:  Sockpuppet detection in wikipedia: A corpus of real-world deceptive writing for linking identities.  CoRR abs/1310.6772 (2013)
  * [5] Yamak, Z., Saunier, J., Vercouter, L.:  Sockscatch: Automatic detection and grouping of sockpuppets in social media.  Knowledge-Based Systems 149 (2018) 124 – 142