# Weak PassPoint Passwords Detected by the Perimeter of Delaunay Triangles

Authors: Lisset Suárez-Plasencia; Carlos Miguel Legón-Pérez; Joaquín Alberto Herrera-Macías; Raisa Socorro-Llanes; Omar Rojas; Guillermo Sosa-Gómez
Journal: Security and Communication Networks
 (2022)

---

## Abstract

PassPoint is a graphical authentication technique that is based on the selection of five points in an image. A detected vulnerability lies in the possible existence of a pattern in the points that make up the password. The objective of this work is to detect nonrandom graphical passwords in the PassPoint scenario. A spatial randomness test based on the average of Delaunay triangles’ perimeter is proposed, given the ineffectiveness of the classic tests in this scenario, which only consists of five points. A state-of-the-art of various applications of Voronoi polygons and Delaunay triangulations are presented to detect clustered and regular patterns. The distributions of the averages of the triangles’ perimeters in the PassPoint scenario for various sizes of images are disclosed, which were unknown. The test’s decision criterion was constructed from one of the best distributions to which the data were adjusted. Type I and type II errors were estimated, and it was concluded that the proposed test could detect clustered and regular graphical passwords in PassPoint, therefore being more effective in detecting clustering than regularity.


---

## Body

## 1. Introduction

Graphical authentication schemes are alternatives to passwords based on alphanumeric characters. These are used in user authentication or key generation for use in cryptographic algorithms [1]. Graphic passwords can be formed by the combination of photos, images, or iconography. Given the characteristics of the images, they produce a much larger password space and are more resistant to dictionary attacks since alphanumeric password phrases that are relatively easy to predict are often used. These passwords’ efficiency is based on the ability of humans to remember patterns in images instead of memorizing sets of characters of great length and complexity.An updated description and critical assessment of the different graphical authentication schemes’ security and usability can be found in [2]. PassPoint is a graphical authentication technique that bases its operation on selecting and remembering patterns of points in images [3]. The authentication process involves the user selecting various points on the image in a particular order. When logging in, the user is supposed to click near the points selected in the registration phase within a tolerance region or neighborhood. One of the vulnerabilities of PassPoint lies in the possible existence of a pattern in the points that make up the password [2]. This pattern can be determined either by selecting the points or by the spatial distribution of them in the image. Considering the latter, a password is considered weak if the points are not randomly distributed and can be obtained by an attacker applying various techniques such as those described in [4–7]. The main types of nonrandomness present between the points, in that case, are clustering, regularity, and smoothness. According to the behavior of the points distributed in the plane (in this case, image), the spatial point patterns are classified into random (homogeneous Poisson point process), regular (uniform or a pattern in inhibition), or clustered (aggregates), [8–12]. During the registration phase of the PassPoint, it is necessary to determine whether the points selected by the user follow a random spatial pattern.In [13], it is stated that Delaunay triangulation and Voronoi polygons have been widely used to analyze the pattern of distribution of points and measure spatial intensity. To measure the distribution of points, we calculate the nearest neighbor and the point pattern shape. When calculating a Voronoi diagram to a point distribution to test the complete spatial randomness of the point distributions, the characteristics of the Delaunay triangles are extracted (e.g., interior angles and edge lengths). Spatial intensity, i.e., how concentrated the points are in a particular study area, is measured by calculating the area and elongation of the Voronoi polygons. This approach has been used in many applications, including agriculture, microbiology, and astronomy [14].In this work, a statistical test is proposed to detect clustering or regularity between the points of a graphical password in PassPoint. This test is based on the Delaunay triangles generated by that password, specifically on the average of those triangles’ perimeters. The effectiveness of the proposed test is experimentally verified. Type I error resulting when applying them to random passwords is estimated and kept at acceptable levels for practical applications; on the other hand, type II error resulting when applied to clustered and regular passwords is estimated, and as expected, it is observed that it depends on the level of clustering or regularity. The article is structured in 4 sections: Section1 shows the Introduction; Section 2 is composed of PassPoint, spatial point patterns, classic tests most used in complete spatial randomness, and the applications of Voronoi diagrams and Delaunay triangulations in the detection of spatial point patterns. Section 3 shows our contribution: detection of weak graphical passwords in PassPoint, based on the perimeter of their Delaunay triangles, and finally in Section 4, the conclusions and future work are presented.


## 2. Preliminaries

### 2.1. PassPoint

PassPoint is a graphical authentication scheme of the cued-recall type presented in [3]. This technique requires the user to select as their password during the registration phase an ordered set of 5 points (pixels) in an image. In the authentication phase, the same points must be selected approximately and in the same order that they were registered. For the authentication process to be effective and convenient for the user, there must be a tolerance associated with each point (approximately 0.25cm). It is possible to use any image to select the password points; it can be provided by the user or the system itself. The authors of this scheme recommend using images that have hundreds of Hotspots spread evenly for greater security. The password is not stored explicitly, but a hash of the concatenation of the password points is generated. However, this causes a problem when applying the password hashing function. It is unlikely that the user will select the same points selected in the authentication phase-image in the registration phase, which means that the password hashing function will always be different. To establish the tolerance around each point, a discretization mechanism is used, which reduces the password space and provides relevant information to carry out a dictionary attack [15]. A discussion about the importance of the discretization mechanism in graphic password schemes can be seen in [16–18], while in [16–19], some of the different methods of discretization known so far are presented.While the selection of images by the user may increase the ability to memorize their password, there is a possibility that, at the same time, security will be compromised with images with few security features (e.g., few memorable points and images that are easy to predict with knowledge about the user) [3]. In several studies such as those presented in [7, 15, 20, 21], dictionary attacks have been carried out using digital image processing techniques. The spatial patterns in the user’s selection of points reduce the effective space of a password and give an advantage to possible attackers, who can use this knowledge to increase their attacks’ probability of success. In the study presented by [22], it is suggested that it is possible to obtain patterns in the shape and order of the selection of the points without knowing the image used to create the password. Users tend to select their password points in separate compositions from the background images, to facilitate the memorability of their passwords. If the set of points selected by the user as their graphical password does not follow a random pattern, it presents a shape of a straight line, curved or by default (Z, W, C, V), or of every 2 consecutive points out of the 5 that make up the password; they are at constant distances. Then, said graphical password is considered weak, as it can be compromised using dictionary attacks [2, 5, 23].


### 2.2. Spatial Point Patterns

The phenomena that occur in some regions of space, such as data on human settlements, animals, the cultivation of crops, or information on the behavior of a pandemic (such as COVID-19 in 2020), represent an occurrence through its spatial coordinatesx,y. The datasets generated by these coordinates are called spatial point patterns [8, 10, 11, 24, 25]. From the study of spatial patterns, inferences can be made about the existence of interactions between each population’s individuals. Spatial point patterns are classified as random (homogeneous Poisson point process), regular (uniform or an inhibiting pattern), or clustered (aggregated); see Figure 1.Figure 1
Random point pattern: (a) regular (b) and clustered (c).
(a)(b)(c)To decide the behavior of an observed point pattern, a complete spatial randomness (CSR) test is applied where it is assumed as a null hypothesis that the pattern comes from the Poisson distribution; that is, that the pattern of points follows a random distribution [8, 26, 27]. The spatial point patterns present two fundamental characteristics [12, 27]. One of them is related to the intensity of the number of points per unit area; the second is based on looking for relationships between each point with those of its surroundings, mainly through the distance between points.


### 2.3. Classic Tests Most Used in Complete Spatial Randomness (CSR)

#### 2.3.1.K-Ripley Function

If a Poisson process randomly distributes a set of points with intensityλ, the expected number of points in a circle of radius r is λπr2. The deviation from randomness can be quantified using the K-Ripley function [8, 25, 27], which reflects the type, intensity, and range of the spatial pattern by analyzing the distances between the points, defined as follows:(1)Kr=An2∑i=1n∑j=1nki,jrei,jr,for all i≠j, where n is the number of points in the pattern, A is the area of the region under study, ei,jr is the edge correction method, and ki,jr is the following indicator function:(2)ki,jr=1,ifri,j≤r,0,ifri,j>r,where ri,j is the distance between points i and j. The edge effects arise because the points that appear outside the limits of the study area are not taken into account to estimate the statistic, even though they are at a distance less than r from a point located within the area. One of the possible expressions of the K-Ripley function, taking into account one of the edge correction methods, is as follows:(3)Kbordr=A∑i=1nξir∑j=1nki,jrn∑i=1nξir,where ξi denotes the indicator function that is equal to 1 if the distance from a point pi to the edge A is greater than or equal to r and 0 otherwise. It is worth clarifying that there are other ways to correct the edge effect, which lead to alternative expressions of the K function. A detailed review of these methods can be found in [8, 28].The transformationL^r=Kr/π allows linearizing the function Kr and stabilizing the variance, and by means of the Lr=L^r−r transformation, it is possible to adjust the Poisson pattern to the value of zero. A clustered pattern occurs when Lr is significantly greater than zero, and a regular pattern occurs when Lr is significantly less than zero.


#### 2.3.2. TheG Function, Distance to the Nearest Neighbor

This method is based on the distances from each point to its nearest neighbor [8, 27]. The expected cumulative distribution function for the nearest neighbor distances d is defined by the Poisson distribution:(4)Gd=1−e−λπd2. If over an area A, n points are randomly distributed, where λ=n/A. To consider the correction of the edge effect, the following function is used:(5)G^d=∑i=1nIidn,where n is the number of points in the pattern and Iid is the indicator function, which takes the value of one if the Euclidean distance between point i and its closest neighbor is less than d, and 0 otherwise; see [8]. A clustered pattern occurs when G^d>Gd, while a regular pattern occurs when G^d>Gd.


#### 2.3.3. The Function F, Distance to the Null Space

The null space distance measures the distanced from each point in an additional m set, called a grid, to the closest of the n points in the observed pattern. For a pattern under the CSR hypothesis, its distribution is the same as for the function Gd, i.e.,(6)Fd=Gd=1−e−λπd2,where λ is the intensity of the pattern. For estimating distances, a set of m points similar to n of the observed pattern is usually used. The distribution of the observed pattern is estimated by(7)F^d=∑j=1mIjdm,where m is the number of points on the grid and Ijd is the indicator function that the value of one if the Euclidean distance between point j on the grid and its closest neighbor in the pattern is less than d, and 0 otherwise.The use of theFd function is similar to that of the Gd function, using Monte Carlo simulations to estimate its critical values and graphical diagnostic tools in the same way. However, the interpretation of the deviations from the observed distribution is opposite: values more significant than those of the theoretical distribution indicate regularity and smaller values indicate clustering. The F function is usually more effective at detecting CSR deviations towards the cluster; see [27].


### 2.4. Applications of Voronoi Diagrams and Delaunay Triangulation in the Detection of Spatial Point Patterns

Voronoi diagrams are geometric structures that allow you to build a partition of the Euclidean plane. Given an initial setP=p1,p2,…,pn of n points in the plane, a Voronoi diagram is defined as a partition of the Euclidean plane into n disjoint regions.Definition (a planar ordinary Voronoi diagram): LetP=p1,p2,…,pn⊂ℜ2, where 2≤n<∞ and pi≠pj, for, i,j∈Jn. We call the region given by(8)Vpi=q:q-pi‖2≤‖q-pi‖2,forj≠i,j∈Jn.The planar ordinary Voronoi polygon associated withpi (or the Voronoi polygon of pi), and the set given by(9)V=Vp1,…,Vpn.The planar ordinary Voronoi diagram byP (or the Voronoi diagram of P): we call pi of Vpi the i th Voronoi polygon, and the set P=p1,p2,…,pn is the generator set of the Voronoi diagram V (in the literature, a generator point is sometimes referred to as a site). [29].For the dual graph of a Voronoi diagram is a Delaunay triangulation, see Figure2. A triangulation of the set P of points on the plane is Delaunay if and only if the circumscribed circumference of any triangle in the lattice does not contain a point of P in its interior. This condition is known as Delaunay’s condition. The Voronoi diagrams and the Delaunay triangulation in the two-dimensional case present a series of characteristics determined by the behavior of the point pattern observed in the initial set of points [9, 29, 30].Figure 2
Representation of a Voronoi diagram (VD) and its corresponding Delaunay triangulation (DT).Since the mid-1980s, some of these characteristics have been used in the study of spatial point patterns. For example, in [31], although the total number of patterns examined is not large, the influence of a Delaunay triangle’s interior angles is studied to detect clustering at the points. In general, the authors concluded that the minimum angle seems preferable to the maximum one to detect clustered or regular patterns. However, there are indications that the maximum angle seems to detect some cases of clustering that are not discernible by the minimum angle. In order to analyze whether the characteristics, interior angle of a Delaunay triangle, minimum angle, mean angle, and maximum angle of a Delaunay triangle, length of one side of a Voronoi polygon, the distance between a site and a vertex of its Voronoi polygon (radius of a circle circumscribed in a Delaunay triangle), length of one side of a Delaunay triangle, and area and perimeter of a Delaunay triangle are capable of detecting nonrandomness. In [9], they generated 100 clustered or regular points in a square unit. Obtaining the characteristic “minimum angle of a Delaunay triangle” is more effective in detecting regular patterns than the others in detecting clustered patterns. An adaptive spatial clustering algorithm based on Delaunay triangulation is proposed in [32]. This algorithm uses both the Delaunay triangulation edge’s statistical characteristics and a new definition of spatial proximity based on the Delaunay triangulation to detect spatial clusters.Discovery of Spatial Patterns with Extended Objects (DEOSP) [33, 34] is another method that allows for the discovery of patterns for extended objects (straight lines, strings of lines, and collections of the same), although it does not allow operating on the extended objects as areas. DEOSP is based on structures related to the Delaunay triangulation. The work presented in [35] uses the area and perimeter of the Voronoi polygons to analyze changes in the spatial patterns of permanent GNSS (Global Navigation Satellite System) stations ASG-EUPOS (Active Geodetic Network-European Position Determination System) in Poland depending on the scales used. Another vital application of Voronoi polygons is the one presented in [36]. In it, the analysis of macromolecular complexes is presented from a method based on 3D Voronoi tessellations. The method enables local density estimation, segmentation, and quantification of 3D particle localization microscopy data; specifically, the authors use the area of Voronoi polygons to detect the clustering of particles.


## 2.1. PassPoint

PassPoint is a graphical authentication scheme of the cued-recall type presented in [3]. This technique requires the user to select as their password during the registration phase an ordered set of 5 points (pixels) in an image. In the authentication phase, the same points must be selected approximately and in the same order that they were registered. For the authentication process to be effective and convenient for the user, there must be a tolerance associated with each point (approximately 0.25cm). It is possible to use any image to select the password points; it can be provided by the user or the system itself. The authors of this scheme recommend using images that have hundreds of Hotspots spread evenly for greater security. The password is not stored explicitly, but a hash of the concatenation of the password points is generated. However, this causes a problem when applying the password hashing function. It is unlikely that the user will select the same points selected in the authentication phase-image in the registration phase, which means that the password hashing function will always be different. To establish the tolerance around each point, a discretization mechanism is used, which reduces the password space and provides relevant information to carry out a dictionary attack [15]. A discussion about the importance of the discretization mechanism in graphic password schemes can be seen in [16–18], while in [16–19], some of the different methods of discretization known so far are presented.While the selection of images by the user may increase the ability to memorize their password, there is a possibility that, at the same time, security will be compromised with images with few security features (e.g., few memorable points and images that are easy to predict with knowledge about the user) [3]. In several studies such as those presented in [7, 15, 20, 21], dictionary attacks have been carried out using digital image processing techniques. The spatial patterns in the user’s selection of points reduce the effective space of a password and give an advantage to possible attackers, who can use this knowledge to increase their attacks’ probability of success. In the study presented by [22], it is suggested that it is possible to obtain patterns in the shape and order of the selection of the points without knowing the image used to create the password. Users tend to select their password points in separate compositions from the background images, to facilitate the memorability of their passwords. If the set of points selected by the user as their graphical password does not follow a random pattern, it presents a shape of a straight line, curved or by default (Z, W, C, V), or of every 2 consecutive points out of the 5 that make up the password; they are at constant distances. Then, said graphical password is considered weak, as it can be compromised using dictionary attacks [2, 5, 23].


## 2.2. Spatial Point Patterns

The phenomena that occur in some regions of space, such as data on human settlements, animals, the cultivation of crops, or information on the behavior of a pandemic (such as COVID-19 in 2020), represent an occurrence through its spatial coordinatesx,y. The datasets generated by these coordinates are called spatial point patterns [8, 10, 11, 24, 25]. From the study of spatial patterns, inferences can be made about the existence of interactions between each population’s individuals. Spatial point patterns are classified as random (homogeneous Poisson point process), regular (uniform or an inhibiting pattern), or clustered (aggregated); see Figure 1.Figure 1
Random point pattern: (a) regular (b) and clustered (c).
(a)(b)(c)To decide the behavior of an observed point pattern, a complete spatial randomness (CSR) test is applied where it is assumed as a null hypothesis that the pattern comes from the Poisson distribution; that is, that the pattern of points follows a random distribution [8, 26, 27]. The spatial point patterns present two fundamental characteristics [12, 27]. One of them is related to the intensity of the number of points per unit area; the second is based on looking for relationships between each point with those of its surroundings, mainly through the distance between points.


## 2.3. Classic Tests Most Used in Complete Spatial Randomness (CSR)

### 2.3.1.K-Ripley Function

If a Poisson process randomly distributes a set of points with intensityλ, the expected number of points in a circle of radius r is λπr2. The deviation from randomness can be quantified using the K-Ripley function [8, 25, 27], which reflects the type, intensity, and range of the spatial pattern by analyzing the distances between the points, defined as follows:(1)Kr=An2∑i=1n∑j=1nki,jrei,jr,for all i≠j, where n is the number of points in the pattern, A is the area of the region under study, ei,jr is the edge correction method, and ki,jr is the following indicator function:(2)ki,jr=1,ifri,j≤r,0,ifri,j>r,where ri,j is the distance between points i and j. The edge effects arise because the points that appear outside the limits of the study area are not taken into account to estimate the statistic, even though they are at a distance less than r from a point located within the area. One of the possible expressions of the K-Ripley function, taking into account one of the edge correction methods, is as follows:(3)Kbordr=A∑i=1nξir∑j=1nki,jrn∑i=1nξir,where ξi denotes the indicator function that is equal to 1 if the distance from a point pi to the edge A is greater than or equal to r and 0 otherwise. It is worth clarifying that there are other ways to correct the edge effect, which lead to alternative expressions of the K function. A detailed review of these methods can be found in [8, 28].The transformationL^r=Kr/π allows linearizing the function Kr and stabilizing the variance, and by means of the Lr=L^r−r transformation, it is possible to adjust the Poisson pattern to the value of zero. A clustered pattern occurs when Lr is significantly greater than zero, and a regular pattern occurs when Lr is significantly less than zero.


### 2.3.2. TheG Function, Distance to the Nearest Neighbor

This method is based on the distances from each point to its nearest neighbor [8, 27]. The expected cumulative distribution function for the nearest neighbor distances d is defined by the Poisson distribution:(4)Gd=1−e−λπd2. If over an area A, n points are randomly distributed, where λ=n/A. To consider the correction of the edge effect, the following function is used:(5)G^d=∑i=1nIidn,where n is the number of points in the pattern and Iid is the indicator function, which takes the value of one if the Euclidean distance between point i and its closest neighbor is less than d, and 0 otherwise; see [8]. A clustered pattern occurs when G^d>Gd, while a regular pattern occurs when G^d>Gd.


### 2.3.3. The Function F, Distance to the Null Space

The null space distance measures the distanced from each point in an additional m set, called a grid, to the closest of the n points in the observed pattern. For a pattern under the CSR hypothesis, its distribution is the same as for the function Gd, i.e.,(6)Fd=Gd=1−e−λπd2,where λ is the intensity of the pattern. For estimating distances, a set of m points similar to n of the observed pattern is usually used. The distribution of the observed pattern is estimated by(7)F^d=∑j=1mIjdm,where m is the number of points on the grid and Ijd is the indicator function that the value of one if the Euclidean distance between point j on the grid and its closest neighbor in the pattern is less than d, and 0 otherwise.The use of theFd function is similar to that of the Gd function, using Monte Carlo simulations to estimate its critical values and graphical diagnostic tools in the same way. However, the interpretation of the deviations from the observed distribution is opposite: values more significant than those of the theoretical distribution indicate regularity and smaller values indicate clustering. The F function is usually more effective at detecting CSR deviations towards the cluster; see [27].


## 2.3.1.K-Ripley Function

If a Poisson process randomly distributes a set of points with intensityλ, the expected number of points in a circle of radius r is λπr2. The deviation from randomness can be quantified using the K-Ripley function [8, 25, 27], which reflects the type, intensity, and range of the spatial pattern by analyzing the distances between the points, defined as follows:(1)Kr=An2∑i=1n∑j=1nki,jrei,jr,for all i≠j, where n is the number of points in the pattern, A is the area of the region under study, ei,jr is the edge correction method, and ki,jr is the following indicator function:(2)ki,jr=1,ifri,j≤r,0,ifri,j>r,where ri,j is the distance between points i and j. The edge effects arise because the points that appear outside the limits of the study area are not taken into account to estimate the statistic, even though they are at a distance less than r from a point located within the area. One of the possible expressions of the K-Ripley function, taking into account one of the edge correction methods, is as follows:(3)Kbordr=A∑i=1nξir∑j=1nki,jrn∑i=1nξir,where ξi denotes the indicator function that is equal to 1 if the distance from a point pi to the edge A is greater than or equal to r and 0 otherwise. It is worth clarifying that there are other ways to correct the edge effect, which lead to alternative expressions of the K function. A detailed review of these methods can be found in [8, 28].The transformationL^r=Kr/π allows linearizing the function Kr and stabilizing the variance, and by means of the Lr=L^r−r transformation, it is possible to adjust the Poisson pattern to the value of zero. A clustered pattern occurs when Lr is significantly greater than zero, and a regular pattern occurs when Lr is significantly less than zero.


## 2.3.2. TheG Function, Distance to the Nearest Neighbor

This method is based on the distances from each point to its nearest neighbor [8, 27]. The expected cumulative distribution function for the nearest neighbor distances d is defined by the Poisson distribution:(4)Gd=1−e−λπd2. If over an area A, n points are randomly distributed, where λ=n/A. To consider the correction of the edge effect, the following function is used:(5)G^d=∑i=1nIidn,where n is the number of points in the pattern and Iid is the indicator function, which takes the value of one if the Euclidean distance between point i and its closest neighbor is less than d, and 0 otherwise; see [8]. A clustered pattern occurs when G^d>Gd, while a regular pattern occurs when G^d>Gd.


## 2.3.3. The Function F, Distance to the Null Space

The null space distance measures the distanced from each point in an additional m set, called a grid, to the closest of the n points in the observed pattern. For a pattern under the CSR hypothesis, its distribution is the same as for the function Gd, i.e.,(6)Fd=Gd=1−e−λπd2,where λ is the intensity of the pattern. For estimating distances, a set of m points similar to n of the observed pattern is usually used. The distribution of the observed pattern is estimated by(7)F^d=∑j=1mIjdm,where m is the number of points on the grid and Ijd is the indicator function that the value of one if the Euclidean distance between point j on the grid and its closest neighbor in the pattern is less than d, and 0 otherwise.The use of theFd function is similar to that of the Gd function, using Monte Carlo simulations to estimate its critical values and graphical diagnostic tools in the same way. However, the interpretation of the deviations from the observed distribution is opposite: values more significant than those of the theoretical distribution indicate regularity and smaller values indicate clustering. The F function is usually more effective at detecting CSR deviations towards the cluster; see [27].


## 2.4. Applications of Voronoi Diagrams and Delaunay Triangulation in the Detection of Spatial Point Patterns

Voronoi diagrams are geometric structures that allow you to build a partition of the Euclidean plane. Given an initial setP=p1,p2,…,pn of n points in the plane, a Voronoi diagram is defined as a partition of the Euclidean plane into n disjoint regions.Definition (a planar ordinary Voronoi diagram): LetP=p1,p2,…,pn⊂ℜ2, where 2≤n<∞ and pi≠pj, for, i,j∈Jn. We call the region given by(8)Vpi=q:q-pi‖2≤‖q-pi‖2,forj≠i,j∈Jn.The planar ordinary Voronoi polygon associated withpi (or the Voronoi polygon of pi), and the set given by(9)V=Vp1,…,Vpn.The planar ordinary Voronoi diagram byP (or the Voronoi diagram of P): we call pi of Vpi the i th Voronoi polygon, and the set P=p1,p2,…,pn is the generator set of the Voronoi diagram V (in the literature, a generator point is sometimes referred to as a site). [29].For the dual graph of a Voronoi diagram is a Delaunay triangulation, see Figure2. A triangulation of the set P of points on the plane is Delaunay if and only if the circumscribed circumference of any triangle in the lattice does not contain a point of P in its interior. This condition is known as Delaunay’s condition. The Voronoi diagrams and the Delaunay triangulation in the two-dimensional case present a series of characteristics determined by the behavior of the point pattern observed in the initial set of points [9, 29, 30].Figure 2
Representation of a Voronoi diagram (VD) and its corresponding Delaunay triangulation (DT).Since the mid-1980s, some of these characteristics have been used in the study of spatial point patterns. For example, in [31], although the total number of patterns examined is not large, the influence of a Delaunay triangle’s interior angles is studied to detect clustering at the points. In general, the authors concluded that the minimum angle seems preferable to the maximum one to detect clustered or regular patterns. However, there are indications that the maximum angle seems to detect some cases of clustering that are not discernible by the minimum angle. In order to analyze whether the characteristics, interior angle of a Delaunay triangle, minimum angle, mean angle, and maximum angle of a Delaunay triangle, length of one side of a Voronoi polygon, the distance between a site and a vertex of its Voronoi polygon (radius of a circle circumscribed in a Delaunay triangle), length of one side of a Delaunay triangle, and area and perimeter of a Delaunay triangle are capable of detecting nonrandomness. In [9], they generated 100 clustered or regular points in a square unit. Obtaining the characteristic “minimum angle of a Delaunay triangle” is more effective in detecting regular patterns than the others in detecting clustered patterns. An adaptive spatial clustering algorithm based on Delaunay triangulation is proposed in [32]. This algorithm uses both the Delaunay triangulation edge’s statistical characteristics and a new definition of spatial proximity based on the Delaunay triangulation to detect spatial clusters.Discovery of Spatial Patterns with Extended Objects (DEOSP) [33, 34] is another method that allows for the discovery of patterns for extended objects (straight lines, strings of lines, and collections of the same), although it does not allow operating on the extended objects as areas. DEOSP is based on structures related to the Delaunay triangulation. The work presented in [35] uses the area and perimeter of the Voronoi polygons to analyze changes in the spatial patterns of permanent GNSS (Global Navigation Satellite System) stations ASG-EUPOS (Active Geodetic Network-European Position Determination System) in Poland depending on the scales used. Another vital application of Voronoi polygons is the one presented in [36]. In it, the analysis of macromolecular complexes is presented from a method based on 3D Voronoi tessellations. The method enables local density estimation, segmentation, and quantification of 3D particle localization microscopy data; specifically, the authors use the area of Voronoi polygons to detect the clustering of particles.


## 3. Detection of Weak Graphical Passwords in PassPoint, Based on the Perimeter of Their Delaunay Triangles

### 3.1. Ineffectiveness of the Classic CSR Tests in the PassPoint Scenario

As far as we are aware of, there is no consensus in the current literature on the minimum value of the number of pointsn of the pattern from which the classic tests described in subsection 2.3 are considered effective. In [37], the authors applied the tests to a pattern of 22 points, the smallest pattern of the reference; however, the results achieved are not discussed. Also, in [37], the authors experimented with a pattern of 36 points, for which they concluded that the tests were effective. So we propose the following research question: what will happen in the PassPoint scenario and where are the patterns with only 5 points available?From the results carried out in [38], it is known that the K-Ripley function tests and those of the distance to the nearest neighbor are ineffective in detecting graphic passwords formed by patterns clustered in PassPoint; however, the experiments were performed for a relatively large number of Monte Carlo simulations. This article analyzes three of the classic tests most used in CSR, including the two tests mentioned above, in detecting nonrandomness in PassPoint passwords, but with a smaller number of Monte Carlo simulations. This difference is given by the existing controversy between the number of simulations in the consulted bibliography, since in [37], the authors state that for a significance level of α=0.05, it is advisable to perform at least 999 simulations, while in [8], they state that for α=0.05 and α=0.01, 40 and 199 Monte Carlo simulations must be performed, respectively.To analyze the detection of nonrandomness of these tests in the PassPoint scenario, two experiments were carried out on a1920×1080 pixel image, one to measure clustering and the other regularity. The experiments carried out were run in MATLAB version R2018a on an AMD A6-9220e CPU: 1.60 GHz with 4 G of RAM.The experiments were designed as follows: for experiment 1, two databases were generated, DB.1.1Ag.IV and DB. 1.2Ag.VIII, of 10,000 passwords with Poisson aggregate patterns with an aggregation distance of 686u and 315u, respectively, [37]. That is, two databases of passwords were generated, clustered in an area equivalent to a quarter of the image and the other to an eighth, containing the DB. 1.2Ag.VIII with a higher level of clustering. The clustered (or aggregated) patterns were derived from a Poisson aggregate process: randomly distributed parental points were generated, and subsequently derived points were randomly distributed around the parents within a specified aggregation radius [8, 37]. For experiment 2, the pattern xy with the highest possible regularity level was generated, which is determined by the following points: 0;0, 1920;0, 0;1080, 1920;1080, and 960;540; see Figure 3.Figure 3
Representation of thexy pattern.Now we discuss the results obtained after running both experiments. For each of the tests, the critical values were estimated using 199 Monte Carlo simulations of sets of 5 random points on a rectangle of size1920×1080. In addition to the K-Ripley function, the confidence intervals were estimated according to Ripley’s approximation +¯1.68A/n [27, 39], where A=1920⋅1080 and n=5. These Monte Carlo simulations guarantee critical intervals with a significance level of α=0.01 for each test. See Figure 4, where the continuous line represents the theoretical value of the null hypothesis, the dashed lines represent the critical values of each of the tests in 199 simulations of random patterns. In the case of the K-Ripley function, the dashed lines represent the confidence intervals for α=0.01 of the test according to Ripley’s approximation. It is observed how the critical values coincide with the minimum value of each function.Figure 4
Critical values of theK-Ripley tests: (a) the nearest neighbor (b) and empty space (c) for 199 Monte Carlo simulations.
(a)(b)(c)From the estimated critical values, an immediate conclusion was obtained: the K-Ripley function tests and the nearest neighbor are not effective in detecting regular patterns, and the null space function test is not very effective in detecting clustered patterns. Furthermore, from the expression of the functionLr, in the K-Ripley function, it is evident that its minimum possible value is Lr=−r. This minimum value coincides with the critical value estimated by the Monte Carlo simulations. Therefore, this test cannot detect a regular pattern since a pattern is considered regular if it is below the critical values estimated by the test. For G^, it holds that G^d≥0, for all d, the lower critical range estimated for the test of the distance to the nearest neighbor is G^d=0 0. Therefore, this test will not be able to detect regular patterns either. Like the G^ function, the minimum value that the F^ function can take is 0. This minimum value coincides with the lower critical value estimated by Monte Carlo simulations. Therefore, this test is not capable of detecting clustered patterns. Of the 10,000 iterations of the F function test for the xy pattern, which expresses the greatest possible regularity between 5 points in a rectangle, it turns out that none of them detects said pattern as regular. These 10,000 iterations are because the F function depends on a grid, which is an additional set of random points; therefore, for a pattern, the value of the function can change depending on the grid. Then the 10,000 iterations were performed for the xy pattern but varying the grid so that the result did not depend on it.The results obtained are summarized in Table1, where t he sign “−” means that the corresponding test is not applicable in the case in question. The results show that the K-Ripley function and the nearest neighbor tests are not effective in detecting clustered 5-point patterns and are not capable of detecting regular 5-point patterns. For its part, the empty space distance test showed an effectiveness of 0% in detecting regular patterns and is unable to detect clustered patterns. Therefore, these three analyzed spatial randomness tests turn out to be ineffective in detecting nonrandom graphical passwords in the scenario PassPoint.Table 1
Percentage of nonrandom graphical passwords detected by each test in each experiment.
TestDB.1.1Ag.IVDB.1.2Ag.VIIIxyNull space——0%K-Ripley5.31%26.55%—Nearest neighbor1.88%8.90%—Recently, in [30], the application of the characteristic “number of sides of the Voronoi polygons” was evaluated for the detection of graphical passwords formed by patterns clustered in PassPoint, but it also proved to be ineffective using the proposed criteria.


### 3.2. The Sample Mean, Sample Variance, and Distribution of the Averages of the Perimeters of the Delaunay Triangles

In Section2.4, we discussed the use of some of the features of Voronoi diagrams and Delaunay triangulations to detect spatial point patterns. In the PassPoint scenario, the points (pixels) of a clustered password are very close between them, and those of a regular graphical password are far from each other for a higher level of consistency. Considering this, in this work, we propose to use the perimeter of the Delaunay triangles to detect randomness between the password points instead of some other characteristic. However, it may be the case that in a password where the points are randomly distributed, the perimeter of one of its Delaunay triangles is just as small as that of one in a clustered password or just as big as one of the triangles of a password with regularly distributed points. In Figure 5, it is observed how the maximum perimeter of the Delaunay triangles of the clustered points coincides with the minimum perimeter of the Delaunay triangles of the random points, as the maximum perimeter of the triangles of Delaunay of the random points coincides with the minimum perimeter of the regular points. This suggests using the average of the perimeters of the Delaunay triangles as decision criteria to detect clustering or regularity between the pixels of a password in PassPoint and not the minimum or maximum value of the Delaunay triangles perimeter.Figure 5
Delaunay triangulations of clustered points (a), random points (b), and regular points (c).
(a)(b)(c)Thus, it is then necessary to determine the probability distribution that best fits the distribution of the average of the perimeters of the Delaunay triangles of a password; for this, experiment 3 was designed and carried out in the following way.1,000 random graphic passwords were generated in each of the three image sizes, 800×480, 1366×768, and 1920×1080 pixels, as the first image is the most common in mobile phones and the other two in computers. For each of these passwords, its Delaunay triangulation is constructed and the average of the perimeters of its Delaunay triangles is calculated, obtaining a total of three random databases of 1,000 averages each. The first database (DB.3.1) contains the averages of the image of 800×480 and the second one (DB.3.2) those of 1366×768, whereas the third one (DB.3.3) contains the averages of the last image. To measure the fit of the data to some known theoretical distribution, the EasyFit 5.6 software was used, which allows the distributions to be automatically adjusted to the sample data and the best model selected in a few seconds [40, 41]. The EasyFit 5.6 consists of 54 theoretical distributions, with some of them for various parameter sets, making a total of 61 possible options to fit for the data.From experiment 3, we obtained the following results. Table2 shows the sample mean and variance corresponding to the averages of the perimeters of the Delaunay triangles for each of the random password databases. Tables 3–5 show the six best models of distributions to which the data were fitted. Table 6 presents the results of the three goodness-of-fit tests applied to the Johnson SB distribution and the estimated distribution of the averages of the perimeters of the Delaunay triangles in each of the random databases corresponding to the sizes of studio images. However, when measuring the adjustment of the 1,000 averages of the perimeters of the Delaunay triangles estimated in each of the random databases to a known theoretical distribution, it was obtained that in each of the databases, it was possible to adjust the averages of the perimeters to more than 20 distributions, with some of them accepted by the three goodness-of-fit tests (Kolmogorov–Smirnov, Anderson–Darling, and Chi-square) with the significance levels α∈0.02,0.01,0.05,0.1,0.2.Table 2
Mean, sample variance, and standard deviation of the averages of the perimeters of Delaunay trianglesPPD in the DBs: 3.1, 3.2, and 3.3, respectively.
PPDDB.3.1DB.3.2DB.3.3EPPD8721,4392,038VPPD39,391102,250210,330σ199,902319,766458,617Table 3
The six best theoretical distributions adjusted by the data from the random database (DB.3.1) with an image size of800×480 pixels using the Kolmogorov–Smirnov (K-S), Anderson–Darling (A-D), and Chi-Square χ2, using the significance levels α∈0.2;0.1;0.05;0.02;0.01, and its p-values associated with the Kolmogorov–Smirnov and Chi-Square tests.
DistributionNumber of acceptancesK–SA-Dχ2Weibull (3P)15/150.98070Accepted0.99858Kumaraswamy15/150.97874Accepted0.99892Gen. Extreme value5/100.94770RejectedN/ALog-Pearson 315/150.94350Accepted0.98486Johnson SB15/150.94114Accepted0.99858Weibull15/150.77054Accepted0.65173Table 4
The six best theoretical distributions adjusted by the data from the random database (DB.3.2) with an image size of1366×768 pixels using the Kolmogorov–Smirnov (K–S), Anderson–Darling (A-D). and Chi-Square χ2, using the significance levels α∈0.2;0.1;0.05;0.02;0.01, and its p-values associated with the Kolmogorov–Smirnov and Chi-Square tests.
DistributionNumber of acceptancesK–SA-Dχ2Johnson SB15/150.95628Accepted0.31172Gen. Extreme value5/100.95460RejectedN/ AKumaraswamy15/150.88420Accepted0.56845Error14/150.87086Acceptedα≠0.20.16329Weibull(3P)15/150.79740Accepted0.50346Log-Pearson 314/150.77399Acceptedα≠0.20.15881Table 5
The six best theoretical distributions adjusted by the data from the random database (DB.3.3) with an image size of1920×1080 pixels using the Kolmogorov–Smirnov (K–S), Anderson–Darling (A-D), and Chi-Square χ2, using the significance levels α∈0.2;0.1;0.05;0.02;0.01, and its p-values associated with the Kolmogorov–Smirnov and Chi-Square tests.
DistributionNumber of acceptancesK–SA-Dχ2Error15/150.99459Accepted0.69818Johnson SB15/150.98592Accepted0.83378Gen. Extreme value15/150.97157Accepted0.74561Log-Pearson 315/150.96973Accepted0.73518Kumaraswamy15/150.90786Accepted0.66530Weibull (3P)15/150.90681Accepted0.55614Table 6
Results of the three goodness-of-fit tests with the significance levelsα∈0.02,0.01,0.05,0.1,0.2, applied to the Johnson SB distribution estimated by the data for each of the random databases DBs: 3.1, 3.2, and 3.3.
Goodness-of-fit testDB.3.1DB.3.2DB.3.3Kolmogorov–Smirnov0.941140.956280.98592Chi-square0.998580.311720.83378Anderson–DarlingAcceptedAcceptedAcceptedNumber of acceptances15/1515/1515/15We now discuss the results of experiment 3. Table2 illustrates that the sample mean and variance differ between the databases due to the inequality between the image sizes. The averages of the perimeters of the Delaunay triangles belonging to the three sizes of the images under study did not fit the distributions with the same parameters (Table 7) or in the same order of the best models fitted by EasyFit, but the fitted distributions for each image size mostly match. Among the best distributions that fit the perimeters of the Delaunay triangles ∀α for the random databases DB.3.1, DB.3.2, and DB.3.3 is the Johnson SB, which occupies the fifth, first, and second place among the best possible models, respectively (Figure 6). This distribution allows for the transformation of the data to a standard normal distribution using the following formula [42]:(10)PDN=JSBPD=γ+δ×lnPD−ξλ+ξ−PD,PDN∼N0,1. This transformation makes it easy to apply normality tests based on the fit of the data. Then, under the randomness hypothesis, the average of the perimeters of the Delaunay triangles of a graphical password in PassPoint when transforming the data to a standard normal distribution is 0. Therefore, it can be assumed that the passwords that violate the above proposition do not follow a random pattern.Table 7
Parameters of the Johnson SB distributionγ,δ,λ,ξ of the averages of the perimeters of the Delaunay triangles in the DBs: 3.1, 3.2, and 3.3, respectively, PPD∼JSBγ,δ,λ,ξ.
DB.Image sizeγδλξDB.3.1800×480−0.449812.78842 295.3−365.06DB.3.21366×768−0.253231.98732 700.28.2037DB.3.31920×1080−0.214582.02833 940.5−30.961Figure 6
Histograms of the averages of the perimeters of the Delaunay triangles associated with the random graphical passwords in DB.3.1 (a), DB.3.2 (b), and DB.3.3 (c), respectively, and their comparison with the Johnson SB.
(a)(b)(c)


### 3.3. Test Based on the Average of the Perimeters of the Delaunay Triangles

In this subsection, we propose a statistical test to detect nonrandom passwords in PassPoint. This test constitutes the main contribution of this article, considering that the classic tests are ineffective in detecting nonrandom graphical passwords in the PassPoint scenario. Although, recently [43], a test (of spatial randomness based on the mean distance between the points) was proposed with the same objective as the test proposed in this work, to detect nonrandom and, therefore, weak graphical passwords introduced by users during the registration phase in a PassPoint system, it is considered necessary to carry out in the next future works a comparison in terms of effectiveness and errors made between these two tests. The proposal of this work consists of a two-tailed hypothesis test based on the average of the Delaunay triangles' perimeters transformed to a standard normal distribution using the Johnson SB transformation. To apply this test, it is necessary to consider the size of the image selected by the user since the Johnson SB parameters are different for the sizes of images analyzed, as shown in Table 7.


#### 3.3.1. Spatial Randomness Test Based on the Average of the Perimeter of Delaunay Triangles to Detect Nonrandom Passwords in PassPoint

We propose the following null hypothesis:(11)H0:EPDN=EJSBPD=0,which states that the graphical password selected by the user is random if the average of the perimeters of the Delaunay triangles transformed by Johnson SB to a standard normal is equal to 0, with an alternative hypothesis given by H1: EPDN=EJSBPD≠0. In order to test the hypothesis, the test statistic, based on the average perimeters of Delaunay triangles of the points of a user-selected password transformed by Johnson SB to a standard normal, is used. It is given by the following:(12)Z=JSBPPD=γ+δ×lnPPD−ξλ+ξ−PPD.From Table7, selecting the values of the transformation parameters depends on the image’s size. The user or system can set the significance level α, whereas the critical region is CR.=z:Z<−zα/2orZ>zα/2. Finally, with respect to the decision criteria, it is decided that the graphical password selected by the user does not follow a random pattern if, when transforming the average of the perimeters of its Delaunay triangles through the Johnson SB transformation, the value obtained belongs to the critical region.


### 3.4. Validation of the Effectiveness of the Proposed Test

To evaluate the effectiveness of the proposed test by means of type I and type II errors, Experiments 4 and 5 were carried out, respectively.To estimate the probabilities of type I error from the proposed decision criterion, experiment 4 was designed. Three new random databases were generated, DB.4.1, DB.4.2, and DB.4.3, with10,000 random graphical passwords each in each of the three image sizes, 800×480, 1366×768, and 1920×1080 pixels, respectively.The results of experiment 4 are shown in Table8. Note that the probability of obtaining the type I error corresponds approximately to the established level of significance (alpha theoretical) for all cases, which shows that the probabilities of type I errors do not seem to depend on the image size and that the proposed decision criterion is valid.Table 8
Estimation of type I error (estimated alpha,α^), that is, of the probability that in DB.4.1, DB.4.2, and DB.4.3, the average of the perimeters of the triangles of a random graphical password belongs to the critical region. Comparison with the preset theoretical alpha α.
α (Theoretical)CR. Of H0α1^α2^α3^∑i=13αi^/3DB.4.1DB.4.2DB.4.30.2Z<−1.282oZ>1.2820.18030.19620.18850.18830.1Z<−1.645oZ>1.6450.08530.10230.09180.09310.05Z<−1.960oZ>1.9600.04030.05450.04990.04820.02Z<−2.326oZ>2.3260.01660.02480.02130.02090.01Z<−2.575oZ>2.5750.00810.01570.01160.0118Now, for experiment 5,50,000 nonrandom graphical passwords are generated in total, 30,000 clustered (10,000 in an area equivalent to a quarter of the image, 10,000 in an area equal to one-sixth of the image, and the other 10,000 in an area equivalent to the eighth of the image), and regular 20,000 (with a lower and higher level of regularity), for each of the study images. This means that, for the 800×480 image, the aggregation distances were 175u, 145u, and 125u radius; for the 1366×768, they were 290u, 240u, and 210u of radius; for the image of 1920×1080, the aggregation distances were 410u, 335u, and 290u of radius, respectively; the regular databases were generated by inhibition distances of 140u and 220u, 210u and 350u, and 300u and 505u of radius, respectively. The regular patterns were derived from a simple inhibition process: random locations of points were generated, verifying that at each new point, the distance to its closest neighbor was equal to or greater than a specified inhibition distance [8, 37]. In each of these databases, the type II error was estimated, and the number of passwords detected was calculated for the different levels of clustering and regularity.The results of experiment 5 are as follows. Figures7 and 8 show the number of nonrandom graphical passwords detected in each of the nonrandom databases for the analyzed image sizes, and Table 9 represents the probabilities of type II errors estimated in nonrandom databases for an image size of 1920×1080.Figure 7
Number of clustered graphical passwords detected (No. of CGPD) in each of the image sizes for clustered pattern databases (in an area equivalent to one-fourth (a), one-sixth (b), and one-eighth (c) of the image), with significance levelα.
(a)(b)(c)Figure 8
Number of regular graphical passwords detected (No. of RGPD) in each of the image sizes for databases with regular patterns (with lower (a) and higher (b) levels of regularity), with significance levelα.
(a)(b)Table 9
Probability estimatedβ^ in DB. 5.1.1Ag.IV, DB. 5.1.2Ag.VI, DB. 5.1.3Ag.VIII, DB. 5.2.1Reg (less regular), and DB. 5.2.2+Reg (more regular) to accept a random graphical password when it is actually a clustered or regular graphical password.
SignificanceError ofβ^β^β^β^β^LevelTipo IIDB.5.1.1Ag.IVDB.5.1.2Ag.VIDB.5.1.3Ag.VIIIDB.5.2.1Reg.DB.5.2.2+Reg0.2−1.282<Z<1.2820.02620.000200.48560.00470.1−1.645<Z<1.6450.12930.003400.59330.05000.05−1.960<Z<1.9600.29820.021900.67290.14360.02−2.326<Z<2.3260.53680.12010.00010.75370.30960.01−2.575<Z<2.5750.68140.24980.00050.80210.4391These results clearly show that by increasing the level of clustering or the regularity level, the test becomes more effective, as was to be expected. The decision criterion is usually quite effective in detecting clustered graphical passwords, especially for the significance levelsα=0.1 and α=0.2 for which it detects 87% and 97% of the passwords, respectively (see Figure 7 and Table 9), in an area equivalent to one-fourth of the image; on the other hand, in the regular graphical passwords with a lower level of regularity, for α=0.2, it only detects approximately 50 of the passwords (see Figure 8 and Table 9). The criterion reaffirms Chiu’s approach in [9], since the average of the Delaunay triangles' perimeters is more effective in detecting clustering than regularity. Figures 7 and 8 show that the probabilities of type II errors do not seem to depend on the image size since their estimated values are similar for the different sizes of images; therefore, only the type II error was shown (Table 9) for each of the nonrandomized study databases of one of the image sizes.This test was designed exclusively to detect graphical passwords with clustered or regular patterns in PassPoint. Therefore, other types of patterns identified in the bibliography [22], such as soft ones or with different predetermined shapes (see Figure 9), will only be detected by the test proposed if these also present a certain level of clustering or regularity (as shown in Figure 10). Therefore, if the patterns are not clustered, it cannot be said that the test can detect these patterns since these patterns have to fulfill the property that when forming their respective Delaunay triangles, one of the interior angles of the triangle has to be obtuse so that the triangle is as devoid of peaks as possible and a relatively smooth curve is formed. Visually, it could be interpreted as patterns in the form of a straight line (or almost straight, given the low probability that the user will select the points of his graphical password in such a way that they form exactly a straight line). This discussion suggests that a test to detect weak passwords can be constructed from the Delaunay triangles’ interior angles, which is left proposed for future work, as well as its comparison with the test proposed in [44].Figure 9
Patterns with different predetermined shapes.Figure 10
Pattern with default shape w, which also follows a clustering pattern (a), the pattern on with default shape (soft) but is detected as random (b), and pattern on with default shape Z, which also follows a regularity pattern (c).
(a)(b)(c)


### 3.5. Comparison in PassPoint of the Proposed Test and the Tests Most Used in CSR

Table10 shows the comparison between the proposed test, the K-Ripley function, the test of the distance to the nearest neighbor, and the empty space function in terms of the effectiveness in the detection of clustered and regular graphical passwords onstage PassPoint, for a significance level of α=0.01.Table 10
Number and proportion of nonrandom graphical passwords detected in the databases DB.1.1Ag.IV, DB. 1.2Ag.VIII, and the regularity pattern xy, by means of the empty space function, the nearest neighbor distance test, the K-Ripley function, and the proposed test.
TestDB.1.1Ag.IVDB.1.2Ag.VIIIxyEmpty space−−0%Nearest neighbor188/10,000=0.0188890/10,000=0.0890−K-Ripley531/10,000=0.05132655/10,000=0.2655−Proposed test3,212/10,000=0.321210,000/10,000=1.0000DetectedThe image size of1920×1080 pixels was used to make this comparison. The results for the other sizes of images studied in this work have a similar behavior. For an image of this size, the average of the perimeters of the Delaunay triangles of the pattern xy is 3,702.9u, whereby transforming this average from a Johnson SB distribution to a standard normal using the statistic Z (12) to get Z=5.6558>2.575=z0.005. Then, by means of the proposed test, the xy pattern is rejected with a 99 confidence, the expected occurrence given its ability to detect regular graphical passwords. This convincingly demonstrates the superiority of the proposed test over the classical tests of spatial randomness to detect nonrandom passwords in PassPoint.


### 3.6. Application of the Proposed Test in PassPoint

In graphical authentication, in the PassPoint scenario, the proposed spatial randomness test allows the user to verify the strength of their password during the registration phase. This is possible due to its ability to detect spatial patterns of clustering or regularity between the points that make up the password. The user must define the level of significance with which they want to verify their password, although it is recommended to useα=0.2 for greater effectiveness. During the PassPoint registration phase, the test can be included by following these steps:Step 1.
The user selects the 5 points (pixels) of his password in an image.Step 2.
Calculate the average of the perimeters of the Delaunay triangles in the password.Step 3.
Calculate the test statisticZ Equation (11) by performing the Johnson SB transformation to the average of the perimeters calculated in Step 2.Step 4.
Determine the critical region taking into account the specified significance level.Step 5.
Decision criteria: if the test statistic calculated in Step 3 does not belong to the critical region, the registration is successfully completed, but if it belongs to the critical region, the user is notified that the password is weak and returns to Step 1.
The proposed test must apply to other systems of the cued-recall type that uses 5 points, or a number close to 5, as its graphical password in an image. The experiments that prove it are left to be published in future research.


## 3.1. Ineffectiveness of the Classic CSR Tests in the PassPoint Scenario

As far as we are aware of, there is no consensus in the current literature on the minimum value of the number of pointsn of the pattern from which the classic tests described in subsection 2.3 are considered effective. In [37], the authors applied the tests to a pattern of 22 points, the smallest pattern of the reference; however, the results achieved are not discussed. Also, in [37], the authors experimented with a pattern of 36 points, for which they concluded that the tests were effective. So we propose the following research question: what will happen in the PassPoint scenario and where are the patterns with only 5 points available?From the results carried out in [38], it is known that the K-Ripley function tests and those of the distance to the nearest neighbor are ineffective in detecting graphic passwords formed by patterns clustered in PassPoint; however, the experiments were performed for a relatively large number of Monte Carlo simulations. This article analyzes three of the classic tests most used in CSR, including the two tests mentioned above, in detecting nonrandomness in PassPoint passwords, but with a smaller number of Monte Carlo simulations. This difference is given by the existing controversy between the number of simulations in the consulted bibliography, since in [37], the authors state that for a significance level of α=0.05, it is advisable to perform at least 999 simulations, while in [8], they state that for α=0.05 and α=0.01, 40 and 199 Monte Carlo simulations must be performed, respectively.To analyze the detection of nonrandomness of these tests in the PassPoint scenario, two experiments were carried out on a1920×1080 pixel image, one to measure clustering and the other regularity. The experiments carried out were run in MATLAB version R2018a on an AMD A6-9220e CPU: 1.60 GHz with 4 G of RAM.The experiments were designed as follows: for experiment 1, two databases were generated, DB.1.1Ag.IV and DB. 1.2Ag.VIII, of 10,000 passwords with Poisson aggregate patterns with an aggregation distance of 686u and 315u, respectively, [37]. That is, two databases of passwords were generated, clustered in an area equivalent to a quarter of the image and the other to an eighth, containing the DB. 1.2Ag.VIII with a higher level of clustering. The clustered (or aggregated) patterns were derived from a Poisson aggregate process: randomly distributed parental points were generated, and subsequently derived points were randomly distributed around the parents within a specified aggregation radius [8, 37]. For experiment 2, the pattern xy with the highest possible regularity level was generated, which is determined by the following points: 0;0, 1920;0, 0;1080, 1920;1080, and 960;540; see Figure 3.Figure 3
Representation of thexy pattern.Now we discuss the results obtained after running both experiments. For each of the tests, the critical values were estimated using 199 Monte Carlo simulations of sets of 5 random points on a rectangle of size1920×1080. In addition to the K-Ripley function, the confidence intervals were estimated according to Ripley’s approximation +¯1.68A/n [27, 39], where A=1920⋅1080 and n=5. These Monte Carlo simulations guarantee critical intervals with a significance level of α=0.01 for each test. See Figure 4, where the continuous line represents the theoretical value of the null hypothesis, the dashed lines represent the critical values of each of the tests in 199 simulations of random patterns. In the case of the K-Ripley function, the dashed lines represent the confidence intervals for α=0.01 of the test according to Ripley’s approximation. It is observed how the critical values coincide with the minimum value of each function.Figure 4
Critical values of theK-Ripley tests: (a) the nearest neighbor (b) and empty space (c) for 199 Monte Carlo simulations.
(a)(b)(c)From the estimated critical values, an immediate conclusion was obtained: the K-Ripley function tests and the nearest neighbor are not effective in detecting regular patterns, and the null space function test is not very effective in detecting clustered patterns. Furthermore, from the expression of the functionLr, in the K-Ripley function, it is evident that its minimum possible value is Lr=−r. This minimum value coincides with the critical value estimated by the Monte Carlo simulations. Therefore, this test cannot detect a regular pattern since a pattern is considered regular if it is below the critical values estimated by the test. For G^, it holds that G^d≥0, for all d, the lower critical range estimated for the test of the distance to the nearest neighbor is G^d=0 0. Therefore, this test will not be able to detect regular patterns either. Like the G^ function, the minimum value that the F^ function can take is 0. This minimum value coincides with the lower critical value estimated by Monte Carlo simulations. Therefore, this test is not capable of detecting clustered patterns. Of the 10,000 iterations of the F function test for the xy pattern, which expresses the greatest possible regularity between 5 points in a rectangle, it turns out that none of them detects said pattern as regular. These 10,000 iterations are because the F function depends on a grid, which is an additional set of random points; therefore, for a pattern, the value of the function can change depending on the grid. Then the 10,000 iterations were performed for the xy pattern but varying the grid so that the result did not depend on it.The results obtained are summarized in Table1, where t he sign “−” means that the corresponding test is not applicable in the case in question. The results show that the K-Ripley function and the nearest neighbor tests are not effective in detecting clustered 5-point patterns and are not capable of detecting regular 5-point patterns. For its part, the empty space distance test showed an effectiveness of 0% in detecting regular patterns and is unable to detect clustered patterns. Therefore, these three analyzed spatial randomness tests turn out to be ineffective in detecting nonrandom graphical passwords in the scenario PassPoint.Table 1
Percentage of nonrandom graphical passwords detected by each test in each experiment.
TestDB.1.1Ag.IVDB.1.2Ag.VIIIxyNull space——0%K-Ripley5.31%26.55%—Nearest neighbor1.88%8.90%—Recently, in [30], the application of the characteristic “number of sides of the Voronoi polygons” was evaluated for the detection of graphical passwords formed by patterns clustered in PassPoint, but it also proved to be ineffective using the proposed criteria.


## 3.2. The Sample Mean, Sample Variance, and Distribution of the Averages of the Perimeters of the Delaunay Triangles

In Section2.4, we discussed the use of some of the features of Voronoi diagrams and Delaunay triangulations to detect spatial point patterns. In the PassPoint scenario, the points (pixels) of a clustered password are very close between them, and those of a regular graphical password are far from each other for a higher level of consistency. Considering this, in this work, we propose to use the perimeter of the Delaunay triangles to detect randomness between the password points instead of some other characteristic. However, it may be the case that in a password where the points are randomly distributed, the perimeter of one of its Delaunay triangles is just as small as that of one in a clustered password or just as big as one of the triangles of a password with regularly distributed points. In Figure 5, it is observed how the maximum perimeter of the Delaunay triangles of the clustered points coincides with the minimum perimeter of the Delaunay triangles of the random points, as the maximum perimeter of the triangles of Delaunay of the random points coincides with the minimum perimeter of the regular points. This suggests using the average of the perimeters of the Delaunay triangles as decision criteria to detect clustering or regularity between the pixels of a password in PassPoint and not the minimum or maximum value of the Delaunay triangles perimeter.Figure 5
Delaunay triangulations of clustered points (a), random points (b), and regular points (c).
(a)(b)(c)Thus, it is then necessary to determine the probability distribution that best fits the distribution of the average of the perimeters of the Delaunay triangles of a password; for this, experiment 3 was designed and carried out in the following way.1,000 random graphic passwords were generated in each of the three image sizes, 800×480, 1366×768, and 1920×1080 pixels, as the first image is the most common in mobile phones and the other two in computers. For each of these passwords, its Delaunay triangulation is constructed and the average of the perimeters of its Delaunay triangles is calculated, obtaining a total of three random databases of 1,000 averages each. The first database (DB.3.1) contains the averages of the image of 800×480 and the second one (DB.3.2) those of 1366×768, whereas the third one (DB.3.3) contains the averages of the last image. To measure the fit of the data to some known theoretical distribution, the EasyFit 5.6 software was used, which allows the distributions to be automatically adjusted to the sample data and the best model selected in a few seconds [40, 41]. The EasyFit 5.6 consists of 54 theoretical distributions, with some of them for various parameter sets, making a total of 61 possible options to fit for the data.From experiment 3, we obtained the following results. Table2 shows the sample mean and variance corresponding to the averages of the perimeters of the Delaunay triangles for each of the random password databases. Tables 3–5 show the six best models of distributions to which the data were fitted. Table 6 presents the results of the three goodness-of-fit tests applied to the Johnson SB distribution and the estimated distribution of the averages of the perimeters of the Delaunay triangles in each of the random databases corresponding to the sizes of studio images. However, when measuring the adjustment of the 1,000 averages of the perimeters of the Delaunay triangles estimated in each of the random databases to a known theoretical distribution, it was obtained that in each of the databases, it was possible to adjust the averages of the perimeters to more than 20 distributions, with some of them accepted by the three goodness-of-fit tests (Kolmogorov–Smirnov, Anderson–Darling, and Chi-square) with the significance levels α∈0.02,0.01,0.05,0.1,0.2.Table 2
Mean, sample variance, and standard deviation of the averages of the perimeters of Delaunay trianglesPPD in the DBs: 3.1, 3.2, and 3.3, respectively.
PPDDB.3.1DB.3.2DB.3.3EPPD8721,4392,038VPPD39,391102,250210,330σ199,902319,766458,617Table 3
The six best theoretical distributions adjusted by the data from the random database (DB.3.1) with an image size of800×480 pixels using the Kolmogorov–Smirnov (K-S), Anderson–Darling (A-D), and Chi-Square χ2, using the significance levels α∈0.2;0.1;0.05;0.02;0.01, and its p-values associated with the Kolmogorov–Smirnov and Chi-Square tests.
DistributionNumber of acceptancesK–SA-Dχ2Weibull (3P)15/150.98070Accepted0.99858Kumaraswamy15/150.97874Accepted0.99892Gen. Extreme value5/100.94770RejectedN/ALog-Pearson 315/150.94350Accepted0.98486Johnson SB15/150.94114Accepted0.99858Weibull15/150.77054Accepted0.65173Table 4
The six best theoretical distributions adjusted by the data from the random database (DB.3.2) with an image size of1366×768 pixels using the Kolmogorov–Smirnov (K–S), Anderson–Darling (A-D). and Chi-Square χ2, using the significance levels α∈0.2;0.1;0.05;0.02;0.01, and its p-values associated with the Kolmogorov–Smirnov and Chi-Square tests.
DistributionNumber of acceptancesK–SA-Dχ2Johnson SB15/150.95628Accepted0.31172Gen. Extreme value5/100.95460RejectedN/ AKumaraswamy15/150.88420Accepted0.56845Error14/150.87086Acceptedα≠0.20.16329Weibull(3P)15/150.79740Accepted0.50346Log-Pearson 314/150.77399Acceptedα≠0.20.15881Table 5
The six best theoretical distributions adjusted by the data from the random database (DB.3.3) with an image size of1920×1080 pixels using the Kolmogorov–Smirnov (K–S), Anderson–Darling (A-D), and Chi-Square χ2, using the significance levels α∈0.2;0.1;0.05;0.02;0.01, and its p-values associated with the Kolmogorov–Smirnov and Chi-Square tests.
DistributionNumber of acceptancesK–SA-Dχ2Error15/150.99459Accepted0.69818Johnson SB15/150.98592Accepted0.83378Gen. Extreme value15/150.97157Accepted0.74561Log-Pearson 315/150.96973Accepted0.73518Kumaraswamy15/150.90786Accepted0.66530Weibull (3P)15/150.90681Accepted0.55614Table 6
Results of the three goodness-of-fit tests with the significance levelsα∈0.02,0.01,0.05,0.1,0.2, applied to the Johnson SB distribution estimated by the data for each of the random databases DBs: 3.1, 3.2, and 3.3.
Goodness-of-fit testDB.3.1DB.3.2DB.3.3Kolmogorov–Smirnov0.941140.956280.98592Chi-square0.998580.311720.83378Anderson–DarlingAcceptedAcceptedAcceptedNumber of acceptances15/1515/1515/15We now discuss the results of experiment 3. Table2 illustrates that the sample mean and variance differ between the databases due to the inequality between the image sizes. The averages of the perimeters of the Delaunay triangles belonging to the three sizes of the images under study did not fit the distributions with the same parameters (Table 7) or in the same order of the best models fitted by EasyFit, but the fitted distributions for each image size mostly match. Among the best distributions that fit the perimeters of the Delaunay triangles ∀α for the random databases DB.3.1, DB.3.2, and DB.3.3 is the Johnson SB, which occupies the fifth, first, and second place among the best possible models, respectively (Figure 6). This distribution allows for the transformation of the data to a standard normal distribution using the following formula [42]:(10)PDN=JSBPD=γ+δ×lnPD−ξλ+ξ−PD,PDN∼N0,1. This transformation makes it easy to apply normality tests based on the fit of the data. Then, under the randomness hypothesis, the average of the perimeters of the Delaunay triangles of a graphical password in PassPoint when transforming the data to a standard normal distribution is 0. Therefore, it can be assumed that the passwords that violate the above proposition do not follow a random pattern.Table 7
Parameters of the Johnson SB distributionγ,δ,λ,ξ of the averages of the perimeters of the Delaunay triangles in the DBs: 3.1, 3.2, and 3.3, respectively, PPD∼JSBγ,δ,λ,ξ.
DB.Image sizeγδλξDB.3.1800×480−0.449812.78842 295.3−365.06DB.3.21366×768−0.253231.98732 700.28.2037DB.3.31920×1080−0.214582.02833 940.5−30.961Figure 6
Histograms of the averages of the perimeters of the Delaunay triangles associated with the random graphical passwords in DB.3.1 (a), DB.3.2 (b), and DB.3.3 (c), respectively, and their comparison with the Johnson SB.
(a)(b)(c)


## 3.3. Test Based on the Average of the Perimeters of the Delaunay Triangles

In this subsection, we propose a statistical test to detect nonrandom passwords in PassPoint. This test constitutes the main contribution of this article, considering that the classic tests are ineffective in detecting nonrandom graphical passwords in the PassPoint scenario. Although, recently [43], a test (of spatial randomness based on the mean distance between the points) was proposed with the same objective as the test proposed in this work, to detect nonrandom and, therefore, weak graphical passwords introduced by users during the registration phase in a PassPoint system, it is considered necessary to carry out in the next future works a comparison in terms of effectiveness and errors made between these two tests. The proposal of this work consists of a two-tailed hypothesis test based on the average of the Delaunay triangles' perimeters transformed to a standard normal distribution using the Johnson SB transformation. To apply this test, it is necessary to consider the size of the image selected by the user since the Johnson SB parameters are different for the sizes of images analyzed, as shown in Table 7.


### 3.3.1. Spatial Randomness Test Based on the Average of the Perimeter of Delaunay Triangles to Detect Nonrandom Passwords in PassPoint

We propose the following null hypothesis:(11)H0:EPDN=EJSBPD=0,which states that the graphical password selected by the user is random if the average of the perimeters of the Delaunay triangles transformed by Johnson SB to a standard normal is equal to 0, with an alternative hypothesis given by H1: EPDN=EJSBPD≠0. In order to test the hypothesis, the test statistic, based on the average perimeters of Delaunay triangles of the points of a user-selected password transformed by Johnson SB to a standard normal, is used. It is given by the following:(12)Z=JSBPPD=γ+δ×lnPPD−ξλ+ξ−PPD.From Table7, selecting the values of the transformation parameters depends on the image’s size. The user or system can set the significance level α, whereas the critical region is CR.=z:Z<−zα/2orZ>zα/2. Finally, with respect to the decision criteria, it is decided that the graphical password selected by the user does not follow a random pattern if, when transforming the average of the perimeters of its Delaunay triangles through the Johnson SB transformation, the value obtained belongs to the critical region.


## 3.3.1. Spatial Randomness Test Based on the Average of the Perimeter of Delaunay Triangles to Detect Nonrandom Passwords in PassPoint

We propose the following null hypothesis:(11)H0:EPDN=EJSBPD=0,which states that the graphical password selected by the user is random if the average of the perimeters of the Delaunay triangles transformed by Johnson SB to a standard normal is equal to 0, with an alternative hypothesis given by H1: EPDN=EJSBPD≠0. In order to test the hypothesis, the test statistic, based on the average perimeters of Delaunay triangles of the points of a user-selected password transformed by Johnson SB to a standard normal, is used. It is given by the following:(12)Z=JSBPPD=γ+δ×lnPPD−ξλ+ξ−PPD.From Table7, selecting the values of the transformation parameters depends on the image’s size. The user or system can set the significance level α, whereas the critical region is CR.=z:Z<−zα/2orZ>zα/2. Finally, with respect to the decision criteria, it is decided that the graphical password selected by the user does not follow a random pattern if, when transforming the average of the perimeters of its Delaunay triangles through the Johnson SB transformation, the value obtained belongs to the critical region.


## 3.4. Validation of the Effectiveness of the Proposed Test

To evaluate the effectiveness of the proposed test by means of type I and type II errors, Experiments 4 and 5 were carried out, respectively.To estimate the probabilities of type I error from the proposed decision criterion, experiment 4 was designed. Three new random databases were generated, DB.4.1, DB.4.2, and DB.4.3, with10,000 random graphical passwords each in each of the three image sizes, 800×480, 1366×768, and 1920×1080 pixels, respectively.The results of experiment 4 are shown in Table8. Note that the probability of obtaining the type I error corresponds approximately to the established level of significance (alpha theoretical) for all cases, which shows that the probabilities of type I errors do not seem to depend on the image size and that the proposed decision criterion is valid.Table 8
Estimation of type I error (estimated alpha,α^), that is, of the probability that in DB.4.1, DB.4.2, and DB.4.3, the average of the perimeters of the triangles of a random graphical password belongs to the critical region. Comparison with the preset theoretical alpha α.
α (Theoretical)CR. Of H0α1^α2^α3^∑i=13αi^/3DB.4.1DB.4.2DB.4.30.2Z<−1.282oZ>1.2820.18030.19620.18850.18830.1Z<−1.645oZ>1.6450.08530.10230.09180.09310.05Z<−1.960oZ>1.9600.04030.05450.04990.04820.02Z<−2.326oZ>2.3260.01660.02480.02130.02090.01Z<−2.575oZ>2.5750.00810.01570.01160.0118Now, for experiment 5,50,000 nonrandom graphical passwords are generated in total, 30,000 clustered (10,000 in an area equivalent to a quarter of the image, 10,000 in an area equal to one-sixth of the image, and the other 10,000 in an area equivalent to the eighth of the image), and regular 20,000 (with a lower and higher level of regularity), for each of the study images. This means that, for the 800×480 image, the aggregation distances were 175u, 145u, and 125u radius; for the 1366×768, they were 290u, 240u, and 210u of radius; for the image of 1920×1080, the aggregation distances were 410u, 335u, and 290u of radius, respectively; the regular databases were generated by inhibition distances of 140u and 220u, 210u and 350u, and 300u and 505u of radius, respectively. The regular patterns were derived from a simple inhibition process: random locations of points were generated, verifying that at each new point, the distance to its closest neighbor was equal to or greater than a specified inhibition distance [8, 37]. In each of these databases, the type II error was estimated, and the number of passwords detected was calculated for the different levels of clustering and regularity.The results of experiment 5 are as follows. Figures7 and 8 show the number of nonrandom graphical passwords detected in each of the nonrandom databases for the analyzed image sizes, and Table 9 represents the probabilities of type II errors estimated in nonrandom databases for an image size of 1920×1080.Figure 7
Number of clustered graphical passwords detected (No. of CGPD) in each of the image sizes for clustered pattern databases (in an area equivalent to one-fourth (a), one-sixth (b), and one-eighth (c) of the image), with significance levelα.
(a)(b)(c)Figure 8
Number of regular graphical passwords detected (No. of RGPD) in each of the image sizes for databases with regular patterns (with lower (a) and higher (b) levels of regularity), with significance levelα.
(a)(b)Table 9
Probability estimatedβ^ in DB. 5.1.1Ag.IV, DB. 5.1.2Ag.VI, DB. 5.1.3Ag.VIII, DB. 5.2.1Reg (less regular), and DB. 5.2.2+Reg (more regular) to accept a random graphical password when it is actually a clustered or regular graphical password.
SignificanceError ofβ^β^β^β^β^LevelTipo IIDB.5.1.1Ag.IVDB.5.1.2Ag.VIDB.5.1.3Ag.VIIIDB.5.2.1Reg.DB.5.2.2+Reg0.2−1.282<Z<1.2820.02620.000200.48560.00470.1−1.645<Z<1.6450.12930.003400.59330.05000.05−1.960<Z<1.9600.29820.021900.67290.14360.02−2.326<Z<2.3260.53680.12010.00010.75370.30960.01−2.575<Z<2.5750.68140.24980.00050.80210.4391These results clearly show that by increasing the level of clustering or the regularity level, the test becomes more effective, as was to be expected. The decision criterion is usually quite effective in detecting clustered graphical passwords, especially for the significance levelsα=0.1 and α=0.2 for which it detects 87% and 97% of the passwords, respectively (see Figure 7 and Table 9), in an area equivalent to one-fourth of the image; on the other hand, in the regular graphical passwords with a lower level of regularity, for α=0.2, it only detects approximately 50 of the passwords (see Figure 8 and Table 9). The criterion reaffirms Chiu’s approach in [9], since the average of the Delaunay triangles' perimeters is more effective in detecting clustering than regularity. Figures 7 and 8 show that the probabilities of type II errors do not seem to depend on the image size since their estimated values are similar for the different sizes of images; therefore, only the type II error was shown (Table 9) for each of the nonrandomized study databases of one of the image sizes.This test was designed exclusively to detect graphical passwords with clustered or regular patterns in PassPoint. Therefore, other types of patterns identified in the bibliography [22], such as soft ones or with different predetermined shapes (see Figure 9), will only be detected by the test proposed if these also present a certain level of clustering or regularity (as shown in Figure 10). Therefore, if the patterns are not clustered, it cannot be said that the test can detect these patterns since these patterns have to fulfill the property that when forming their respective Delaunay triangles, one of the interior angles of the triangle has to be obtuse so that the triangle is as devoid of peaks as possible and a relatively smooth curve is formed. Visually, it could be interpreted as patterns in the form of a straight line (or almost straight, given the low probability that the user will select the points of his graphical password in such a way that they form exactly a straight line). This discussion suggests that a test to detect weak passwords can be constructed from the Delaunay triangles’ interior angles, which is left proposed for future work, as well as its comparison with the test proposed in [44].Figure 9
Patterns with different predetermined shapes.Figure 10
Pattern with default shape w, which also follows a clustering pattern (a), the pattern on with default shape (soft) but is detected as random (b), and pattern on with default shape Z, which also follows a regularity pattern (c).
(a)(b)(c)


## 3.5. Comparison in PassPoint of the Proposed Test and the Tests Most Used in CSR

Table10 shows the comparison between the proposed test, the K-Ripley function, the test of the distance to the nearest neighbor, and the empty space function in terms of the effectiveness in the detection of clustered and regular graphical passwords onstage PassPoint, for a significance level of α=0.01.Table 10
Number and proportion of nonrandom graphical passwords detected in the databases DB.1.1Ag.IV, DB. 1.2Ag.VIII, and the regularity pattern xy, by means of the empty space function, the nearest neighbor distance test, the K-Ripley function, and the proposed test.
TestDB.1.1Ag.IVDB.1.2Ag.VIIIxyEmpty space−−0%Nearest neighbor188/10,000=0.0188890/10,000=0.0890−K-Ripley531/10,000=0.05132655/10,000=0.2655−Proposed test3,212/10,000=0.321210,000/10,000=1.0000DetectedThe image size of1920×1080 pixels was used to make this comparison. The results for the other sizes of images studied in this work have a similar behavior. For an image of this size, the average of the perimeters of the Delaunay triangles of the pattern xy is 3,702.9u, whereby transforming this average from a Johnson SB distribution to a standard normal using the statistic Z (12) to get Z=5.6558>2.575=z0.005. Then, by means of the proposed test, the xy pattern is rejected with a 99 confidence, the expected occurrence given its ability to detect regular graphical passwords. This convincingly demonstrates the superiority of the proposed test over the classical tests of spatial randomness to detect nonrandom passwords in PassPoint.


## 3.6. Application of the Proposed Test in PassPoint

In graphical authentication, in the PassPoint scenario, the proposed spatial randomness test allows the user to verify the strength of their password during the registration phase. This is possible due to its ability to detect spatial patterns of clustering or regularity between the points that make up the password. The user must define the level of significance with which they want to verify their password, although it is recommended to useα=0.2 for greater effectiveness. During the PassPoint registration phase, the test can be included by following these steps:Step 1.
The user selects the 5 points (pixels) of his password in an image.Step 2.
Calculate the average of the perimeters of the Delaunay triangles in the password.Step 3.
Calculate the test statisticZ Equation (11) by performing the Johnson SB transformation to the average of the perimeters calculated in Step 2.Step 4.
Determine the critical region taking into account the specified significance level.Step 5.
Decision criteria: if the test statistic calculated in Step 3 does not belong to the critical region, the registration is successfully completed, but if it belongs to the critical region, the user is notified that the password is weak and returns to Step 1.
The proposed test must apply to other systems of the cued-recall type that uses 5 points, or a number close to 5, as its graphical password in an image. The experiments that prove it are left to be published in future research.


## 4. Conclusions and Future Work

In this work, it was shown that three of the most used classical tests in complete spatial randomness are inefficient in detecting nonrandom passwords in the PassPoint scenario, so the average of the perimeters of the Delaunay triangles was investigated to extract dependency information between password points. Its distribution was estimated in each of the random databases, which was adjusted to more than 20 known distributions for each of the study image sizes, the Johnson SB distribution for each image being among the five best fits. Different parameters of the Johnson SB distribution were obtained from the averages of the perimeters of the Delaunay triangles for the three sizes of images analyzed. Therefore, it was assumed with an established significance level that graphical passwords that violate this property are not random. The application of this criterion is facilitated because after applying the Johnson SB transformation with the parameters of the Johnson SB distribution established for each image size, the transformed average must follow a standard normal distribution. Based on the average of the Delaunay triangles perimeters transformed to a standard normal distribution by the Johnson SB transformation, a test was proposed to detect weak graphical passwords formed by clustered or regular points. Type I and type II errors were estimated, and the number of graphical passwords detected by this test was calculated for various levels of clustering and regularity. It was concluded that regardless of the image size, their estimates of type I and type II errors roughly coincide for an established level of significance and thus, the number of passwords detected. It is concluded that the proposed criterion based on the average of the perimeters of the Delaunay triangles is efficient for detecting weak graphical passwords in PassPoint, formed by five clustered points or by five regular points, although it is more precise in detecting clustering than regularity. Despite the effectiveness of the proposed test being tested for various levels of clustering or regularity, with different type II errors, the minimum level of clustering or regularity for which the test’s effectiveness remains acceptable in application practices is still unknown. This aspect will be investigated in future work. Another open problem that will be discussed soon is the reduction of type II errors. The proposed 2-tailed test assesses deviations from randomness, and its effectiveness was evaluated in the detection of two types of patterns, clustered or regular. If hypotheses of the typeH1: clustered or H1: regular are considered separately as alternative hypotheses, a one-tailed test will be obtained in each case, and a reduction of the type II error can be expected. This approach has the limitation of evaluating the existence of a specific type of nonrandom pattern, and a different test should be applied for each type of pattern. Its advantage is that it can be more effective in determining the type of pattern once it is decided to reject randomness. In future works, experiments will be carried out to evaluate the proposed test to detect passwords formed by soft patterns or with different predetermined forms. Another aspect to evaluate is the comparison in terms of effectiveness and errors made of the proposed test and the spatial randomness test based on the mean distance between the points. In addition, combinations of the different tests will be analyzed to increase the effectiveness in detecting nonrandom passwords without significantly compromising the implementation time. It is also proposed to evaluate the effectiveness of other characteristics of Delaunay triangulation to detect patterns in PassPoint, such as the minimum angle of a Delaunay triangle to detect regularity



---

*Source: 3624587-2022-09-21.xml*