Enhanced detection of regular graphical passwords in Passpoints through convex hull area analysis

1 Introduction

Authentication is imperative for the security of contemporary digital information processing services. Alphanumeric passwords, which combine letters and digits, have historically dominated authentication methods. However, there is an urgent need for alternative methods due to the inherent weaknesses that arise when a user creates their password (David and Wool, 2021; Awan et al., 2021; Nosenko et al., 2022) and because using the same password on different websites makes them vulnerable to various attacks, such as those based on probabilistic models (Legón, 2019) and, more recently, on the use of artificial intelligence, such as GPT chat (Rando et al., 2024); indeed, dedicated large-language-model password guessers have recently been shown to raise this threat further (Zou et al., 2025).

Among the alternative methods proposed in the literature, biometric authentication (Bhattacharyya et al., 2009; Pahuja and Goel, 2024) and graphic authentication (Wiedenbeck et al., 2005) stand out for their security and usability. Both approaches leverage human capabilities: biometric systems rely on the uniqueness of each individual. At the same time, graphic authentication exploits the ease with which people remember images or parts of them relative to complex character strings. Each approach has advantages and disadvantages in today's digital environments. While biometrics offers a high level of security, its implementation entails hardware costs and raises challenges regarding revocability and privacy. In contrast, graphic authentication offers an optimal balance between security, usability, and low implementation cost, making it particularly attractive in contexts with economic constraints. Graphical authentication remains an active area of research, with recent schemes based on fast object detection (Ray et al., 2023), neural style transfer on smartphones (Ray et al., 2025), and dynamic pattern designs (Andriotis et al., 2022).

In Floch et al. (2018); Rodriguez Valdés et al. (2018), a comparative analysis of existing graphical authentication methods was conducted, highlighting the Passpoints method for its balance between security and ease of use. More recent systematic reviews corroborate this balance and survey the security attacks and countermeasures relevant to these schemes (Binbeshr et al., 2024; Por et al., 2024). Passpoints were developed by Wiedenbeck et al. (2005) based on the observation that humans memorize images or parts of them more quickly and easily than highly complex character strings. During the registration phase, the user must select five points in an image, in a specific order, to form their password. During authentication, the user must click on the same points and in the same order, within a tolerance margin defined by the system.

However, if users choose passwords that follow predictable patterns, the system's security may be compromised (Valdés et al., 2019; Chiasson et al., 2009). This problem has led to the development of statistical tests to detect these weaknesses during the registration phase (Herrera-Macías et al., 2021; Suárez-Plasencia et al., 2022b; Herrera Macías et al., 2023; Herrera-Macías et al., 2024; Suárez-Plasencia et al., 2022a), thereby preventing potential attacks on the system (Thorpe and van Oorschot, 2007; van Oorschot et al., 2010; van Oorschot and Thorpe, 2011). Among the different types of patterns identified in the literature (Valdés et al., 2019; Chiasson et al., 2009), the following stand out: clustered patterns, regular patterns, and LINE and DIAG patterns (straight line alignments).

The most effective tests in detecting non-random patterns in Passpoints passwords are: the mean distance-based test for detecting regular patterns (12), the convex hull perimeter-based test for detecting clustered patterns (15), and the test based on the maximum angles of Delaunay triangles for detecting DIAG and LINE patterns (16). However, these figures are not directly comparable, since they correspond to different significance levels and different levels of regularity. For the significance level α = 0.1 recommended by the authors in Herrera-Macías et al. (2021), the previous mean-distance test detects 60% of regular passwords at the lowest level of regularity analyzed and 98% at the highest. Under matched conditions, however, the test proposed here is uniformly superior, as summarized in Table 1: it is not the case that a previous test attains 98% while ours attains only 80% under the same conditions, since the 98% figure corresponds to the previous test at the highest regularity level, whereas the 80% figure corresponds to the proposed test at α = 0.05 (a stricter level, i.e., fewer false positives) at the hardest regularity level. Therefore, this work aims to increase the detection rate of regular patterns in Passpoints graphic passwords, raising it to a level comparable with that achieved for other pattern types.

Table 1. Percentage of regular passwords detected by the proposed test (test 1) and the mean-distance baseline (test 2) under matched significance and regularity levels.

In this work the full range α∈{0.01, 0.02, 0.05, 0.1, 0.2} is evaluated. The significance level α is the false-positive (Type I) rate of the test: the fraction of legitimate, random passwords that are wrongly flagged as regular and asked to be re-selected during registration. While Herrera-Macías et al. (2021) recommends α = 0.1, we recommend α = 0.05 as the operating point for general-purpose deployment, since it halves the usability cost (from one re-registration in ten to one in 20) while still detecting 80% of regular passwords at the hardest regularity level. Thus α is a tunable security/usability trade-off rather than a fixed choice. To this end, we propose a statistical test that computes the area of the convex hull of the five points selected by the user as their graphical password. This test will be integrated into the recently developed Passpoints API in Sánchez et al. (2024), which is publicly available at: https://alexsanchez-bit.github.io/Passpoints-test/#/.

This proposal is based on the definition of the convex hull of n points in the plane, derived from computational geometry (Li and Klette, 2011; Rockafellar, 1997; de Berg et al., 2008). Although its efficient implementation is an active area of research (Candela et al., 2022; Tabacman, 2021; Keith et al., 2022) with applications across various fields, there is a scarcity of references to applications in security, such as the one presented in this paper. There are several algorithms for calculating the convex hull, with complexities of the order of O(n³), O(n²), and O(nlogn). However, in the specific scenario considered in this research, where n is a fixed number of 5 randomly distributed points, the complexity can be reduced to a constant function, O(1). The cost of processing a database of m passwords is therefore a linear function O(m).

The main characteristics of the convex hull of a set of points in the plane are its perimeter, its area, and the number of vertices. Studies have been conducted on its statistical properties as the number of points tends to infinity (Khamdamov and Chay, 2022). It is also possible to calculate the convex hull of a random walk defined by an ordered set of points, and the statistical properties of such a hull have also been investigated (McRedmond and Wade, 2018). Although the exact distribution functions for the area of the convex hull of 3 and 4 random points in a square are known (Philip, 2004), a closed-form expression for n = 5 (and small n in general) has not been found in the literature.

The use of the convex hull in graphical authentication has a well-documented trajectory. The pioneering work of Sobrado and Birget (2002) proposed a human identification protocol based on the convex hull, a concept later taken up by Man et al. (2003) in 2003, transforming it into a challenge-response system known as WIW. It was ultimately formalized and rigorously evaluated by Wiedenbeck et al. (2005), where Sobrado and Birget appear as co-authors, proposing the Convex Hull Click scheme (Wiedenbeck et al., 2006). More recently, Bostan and Bostan (2023) revisited the idea and proposed the Randomized Pass Points scheme, which introduces randomization in point positions to resist shoulder-surfing attacks. However, all of these works use the convex hull as an authentication mechanism. Our approach is radically different and novel: we propose the area of the convex hull as a test statistic to detect regular patterns in Passpoints graphical passwords during the registration phase. This vulnerability had not been addressed from this statistical perspective. Figure 1 shows a Passpoints process pipeline with the proposed approach based on the convex hull.

To perform the test comparison, all implementations and experiments were developed in MATLAB R2018a on a laptop PC with an AMD Athlon Silver 3050U processor (2.30 GHz) and 8GB of RAM. The work is structured into three sections: the first presents the introduction; the second presents our contribution: a new test to detect regular graphical passwords in Passpoints, as well as a comparison with previous tests; finally, the third presents the conclusions and future work.

2 Our contribution: a test to detect regular patterns in Passpoints graphical passwords based on the convex hull area

The methodological approach followed in this work focuses on measuring the area of the convex hull (A_*CH*) as the main discriminant variable for sample classification. The methodology is as follows: The probability distribution governing the convex-hull area characteristic is determined using 5 randomly distributed points. Next, a hypothesis test is performed to classify individual samples, and a three-region decision scheme based on percentiles of the estimated probability distribution is implemented. Samples are categorized as regular if they fall within the right tail of the distribution. Finally, the Type I and Type II errors of the test are estimated from the experiment.

2.1 Hypothesis proposed

The convex hull of a set of points in the plane can be intuitively defined as the elastic band that surrounds the points, fitting exactly to their contours; that is, the convex hull of a set of points determines the smallest convex polygon that encloses those points. It is intuitive to think that if the points are spread out, the polygon enclosing them will be larger, and therefore the area delimited by the convex hull will increase. This increase would be even more evident in a context with few points, as is the case with Passpoints.

This intuitive idea coincides with the strictly geometric characterization of a regular pattern: we understand a regular pattern as one in which its points repel each other, that is, they tend to maximize mutual distance and, consequently, the area of the convex hull they delimit. This contrasts with clustered patterns, where points tend to concentrate, and random patterns, where they follow a uniform and independent distribution. This definition is independent of any human perception of the shape of the pattern; it is a statistical property of the spatial configuration of the points. Therefore, the hypothesis is proposed to use the area of the convex hull delimited by the five points of a graphical password in Passpoints as a statistic of the regularity measure of the points. Figure 2 shows the convex hull determined by three graphical passwords with clustering (Figure 2a), randomness (Figure 2b), and regularity (Figure 2c) patterns, respectively. The figure supports the proposed hypothesis; note the difference in the areas of the convex hulls.

It is imperative to determine the probability distribution that best captures the area of the convex hull defined by five points randomly distributed across the image. This understanding would facilitate the formulation of a hypothesis test that distinguishes among the three potential patterns at a pre-specified alpha level.

Beyond the visual intuition of Figure 2, the discriminating power of the convex-hull area follows from the mechanism that generates regular patterns. In a regular configuration the selected points repel one another and no two lie closer than an inhibition distance d, so the points are forced apart and the polygon they delimit expands. The mean area of the convex hull is therefore larger under a regular mechanism than under complete spatial randomness, and increases with the degree of regularity imposed. It should be noted that d is a lower bound on the pairwise distances rather than a complete description of the configuration: two generating mechanisms sharing the same d may produce very different dispersions, so A_*CH* responds to the generating mechanism as a whole and not to d alone.

Figure 3 illustrates this separation directly, using the databases employed in the evaluation rather than a schematic model. Under complete spatial randomness the mean convex-hull area is 4.55 × 10⁵ px², close to the mean bΓ(1+1/a) = 4.44 × 10⁵ px² of the fitted Weibull law. In DB.3.1 (Regular) the mean rises to 11.97 × 10⁵ px² and in DB.3.2 (Regular+) to 14.91 × 10⁵ px², that is, to 58% and 72% of the total image area. The dashed lines mark the critical values at α = 0.05. The separation between the null distribution and the two regular populations is what the proposed test exploits, and the residual overlap on the left of the upper critical value is precisely the Type II error reported in Table 2.

Table 2. Estimated probability (β^) of type II error.

It is worth noting why this relationship must be characterized empirically. The exact distribution of the area of the convex hull of n uniformly random points in a rectangle is known in closed form only for n = 3 and n = 4 (Philip, 2004); for n = 5, in the case fixed by the Passpoints scheme, no closed-form expression is available. This is the reason the reference distribution is estimated by simulation and fitted to a Weibull model, rather than derived analytically. It is the technical obstacle that distinguishes the small-n regime studied here from the asymptotic results (n → ∞) available in the literature (Khamdamov and Chay, 2022; McRedmond and Wade, 2018).

2.2 Estimation of the probability distribution of the area of the convex hull

To determine the probability distribution of the area of the convex hull of 5 points uniformly distributed over an image of size 1, 920 × 1, 080, the following experiment was performed.

2.3 Experiment 1

The evaluation is organized into three experiments with distinct roles. Experiment 1 estimates the null (reference) distribution of the convex-hull area A_*CH* under complete spatial randomness, which is required to define the critical regions of the test. Experiment 2 validates the Type I error (false-positive rate) of the test on random passwords. Experiment 3 measures the Type II error, i.e., the detection power of the test, on regular passwords. Experiments 1, 2 therefore concern random patterns, and only Experiment 3 concerns regular patterns.

The experiment consisted of simulating 1, 000 independent graphical passwords in MATLAB R2018a. Each password was generated by drawing five independent points from a uniform distribution over the 1, 920 × 1, 080 image, i.e., under complete spatial randomness (CSR). This uniform sampling mechanism defines the null hypothesis H₀ of the test. The areas of the convex hulls defined by each of these passwords were calculated, and a database (DB.1) containing 1, 000 real values was obtained for analysis. EasyFit v.5.6 was used to assess the compatibility of the data with the specified probability distributions.

2.4 Results of experiment 1

The data showed a good fit to the Weibull distribution with parameters a = 2.2478, b = 5.0076E+5. Figure 4 illustrates the fit of the Weibull distribution to the data. To measure the fit of the data, three well-known goodness-of-fit tests were used: Anderson-Darling, Kolmogorov-Smirnov, and Chi-Square; the results of these tests are shown in Table 3.

Table 3. Results of the goodness-of-fit tests applied to the Weibull distribution estimated from the data contained in DB.1, for the significance levels α∈{0.02, 0.01, 0.05, 0.1, 0.2}.

DB.1 was regenerated and enlarged to 10⁶ random passwords so that the reference distribution would not itself be a source of calibration error; the re-estimated parameters are those of Table 4. At this sample size the goodness-of-fit tests reject the Weibull model, which is the expected consequence of their power growing with n: the Weibull is a close approximation to the distribution of A_*CH* but not its exact law. We therefore retain it as the closed-form description of the reference distribution, which is what permits the extension to other resolutions through the q² scaling of b, while the critical regions used in the test are computed as empirical quantiles of the Monte Carlo reference sample, so that the nominal significance levels are attained without relying on the exactness of the parametric form. The goodness-of-fit analysis reported below is carried out on a sub-sample of 1, 000 observations, matching the size used in the original version of this work, and is to be read as an assessment of the adequacy of the approximation at that scale rather than as a claim that the law is exactly Weibull. Because the Weibull parameters were estimated from DB.1 itself, the tabulated null distributions of the Kolmogorov–Smirnov and Anderson–Darling statistics do not apply. Fitting the parameters to the sample draws the fitted distribution function toward the empirical one, so both statistics are stochastically smaller under H₀ than the tabulated laws assume, and the corresponding p-values are inflated rather than conservative. We therefore obtained p-values by a parametric bootstrap with B = 2, 000 replicates, re-estimating the parameters on each replicate. The bootstrap 95th percentile of D is appreciably below its asymptotic counterpart, which quantifies the magnitude of the effect. Under the correct null distribution the Weibull model is not rejected, so the conclusion of the original analysis is unchanged, although the evidence is weaker than the naive p-values suggested. For the Chi-square test the sample was divided into k equiprobable classes following Sturges' rule, which keeps the expected frequencies adequate, and the degrees of freedom are reduced by two to account for the estimated parameters. The Anderson–Darling test weights the tails more heavily, which is directly relevant here because the critical regions of the proposed test lie in the tails. We note, however, that at n = 1, 000 these tests have limited power against moderate tail misspecification, so acceptance of the Weibull model does not by itself guarantee that the nominal significance levels are attained exactly; this is examined directly in Experiment 2.

Table 4. Weibull distribution parameters (a, b) estimated from DB.1.

The Weibull model was accepted along with five others; however, it obtained the best p-value in the Kolmogorov-Smirnov test and was therefore ranked as the best fit. This test was selected as the benchmark because it is suitable for both small and large samples and provides a global measure of the discrepancy between the empirical and theoretical distributions. The top 10 best fits of the data can be consulted in Figure 5.

Given these results, it is assumed that the sought distribution is a Weibull with parameters shown in Table 4.

Taking the 1, 920 × 1, 080 case as a baseline, the test can be extended to other resolutions with a 16:9 aspect ratio without the need to repeat the simulations. Since the area of the convex hull is a two-dimensional magnitude that scales quadratically with the image dimensions, and the Weibull distribution is closed under linear transformation, in particular under scaling. It follows that if A_*CH*~W(a, b) then the scaled image satisfies q2·ACH~W(a,q2b), where q is the scale factor between one resolution and another. It is sufficient to scale the parameter b by the factor q² to extend it to other image sizes.

2.5 Formalization of the proposed method

Once the reference distribution has been established, the task is to decide whether a single observation, the A_*CH* of a user-selected password, is plausible under it. We emphasize that this decision procedure is not itself a goodness-of-fit test. A goodness-of-fit test evaluates whether a sample is compatible with a distributional family, and its statistics are functionals of the empirical distribution function, which is not informative for a single observation. What is proposed here is a one-sided tail test of an individual observation against a fully specified reference distribution—a discordancy test in the sense of Barnett and Lewis (1994). The test is one-sided because a regular pattern can only inflate the area of the convex hull: points that repel one another spread further apart and enclose a larger polygon. Placing half of the significance level in the lower tail would therefore spend it on a region that regular configurations never occupy, and in the databases used in Experiment 3 not a single regular password falls below the lower critical value at any of the significance levels considered. The null hypothesis is that the password was generated under complete spatial randomness; the test statistic is A_*CH*; and the null distribution is the distribution of A_*CH* under CSR, estimated in Experiment 1. Goodness-of-fit testing enters this work only in Experiment 1, where it is applied to a sample of 1, 000 areas to select and validate that approximation. The significance level α therefore retains its usual meaning: the probability that a password generated under CSR falls in the critical region and is flagged for re-selection. The reference implementation released with this work applies exactly this rule.

The significance levels α∈{0.02, 0.01, 0.05, 0.1, 0.2} are established, and the percentiles at level α for the Weibull distribution are found using the inverse cumulative distribution function:

F-1(p)=b[-Ln(1-p)]1/a,(1)

using the parameters in Table 4. To apply this test, the user-selected image size must be taken into account, as the estimated parameters of the Weibull distribution depend on it.

2.5.1 Definition of the proposed test

The proposed test evaluates whether an individual password's A_*CH* is plausible under the reference Weibull distribution. The null hypothesis is proposed.

• H₀: the five points were generated under complete spatial randomness,

that is, the graphical password selected by the user follows a random pattern, so that under H₀ its area satisfies A_*CH*~W(a, b) with the parameters of Table 4. As an alternative hypothesis

• H₁: the five points enclose a larger area than expected under complete spatial randomness,

that is, the password follows a regular pattern. The critical region is accordingly Z>F⁻¹(1−α), a single upper tail of probability α. If the value lies in the left tail of the Weibull distribution, this suggests a clustering pattern; if it lies in the right tail, it suggests a regular pattern. As a statistic, the A_*CH* value for the sample is compared directly to the Weibull distribution, given that the population follows a Weibull distribution.

Z=ACH

with the selection of parameter values according to the image size. As a critical region

{Z:Z<F-1(α/2)∪Z>F-1(1-α/2)}

in practical terms, F⁻¹(α/2) and F⁻¹(1−α/2) are the percentiles α/2 and 1−α/2 respectively of the Weibull distribution, and α is the significance level previously set by the user or system.

2.5.2 Evaluation of the effectiveness of the proposed test

The authors highlight that, according to the test definition, obtaining A_*CH* values located in the left tail of the Weibull distribution would indicate a clustering pattern. However, the results obtained in this respect during the experiments are not statistically significant relative to those reported in the background, so they are not relevant to the present article. This section only reports the results concerning the detection of regular patterns, which constitutes the main contribution of this work.

To evaluate the effectiveness of the proposed test, the Type I and Type II errors are estimated. The following experiments are performed for this purpose.

2.6 Experiment 2

To estimate the probability of committing a Type I error, 10, 000 new graphical passwords were simulated, with points randomly distributed across the image. These passwords are grouped in the database denoted as DB.2. All simulations were carried out in MATLAB R2018a, and the distribution fitting reported in Experiment 1 was performed with EasyFit v5.6. The 10, 000 random passwords in database DB.2 were generated by uniform i.i.d. sampling (CSR), as in Experiment 1. The proposed test was applied to each of these passwords, and the number of false positives obtained for the significance levels α∈{0.2, 0.1, 0.05, 0.02, 0.01}. For each estimate, 95% confidence intervals were calculated using the Wilson method (CI 95% Wilson).

The results of Experiment 2 are summarized in the following Table 5.

Table 5. Estimate of the type I error committed by the test (α^) against the expected theoretical error (α).

Table 5 shows that the observed estimates deviate slightly from the theoretical values, with discrepancies of less than 0.02, which we attribute to sampling variability. The 95% Wilson intervals are consistent with the nominal levels. This close calibration of the Type I error validates the Weibull reference distribution and, crucially, is the precondition for interpreting the detection (Type II) results of Experiment 3: an overstated or understated false-positive rate would invalidate any power comparison. This good fit validates the methodology used so far in defining the proposed test. It allows for accurate estimation of the false positives committed by the test in detecting regular patterns.

2.7 Experiment 3

To evaluate the effectiveness of the proposed test in detecting regular graphical passwords, a total of 20, 000 graphical passwords were generated, distributed across two levels of regularity. The regular passwords in DB.3.1 and DB.3.2 were generated in MATLAB R2018a with the construction introduced in Herrera-Macías et al. (2021) and Suárez-Plasencia et al. (2022b), reproduced here without modification so that the Type II errors of the proposed test and of the mean-distance baseline are directly comparable. The construction imposes an exact central symmetry: the five points consist of one point close to the center of the image together with two pairs placed antipodally about that center, subject to the constraint that no two points lie closer than an inhibition distance d. In the resulting databases the minimum pairwise distance equals d exactly (300 px in DB.3.1, 504 px in DB.3.2), while the mean minimum pairwise distance is considerably larger (647 and 816 px respectively), because the symmetry constraint, rather than the inhibition distance alone, governs the dispersion of the configuration. This is a stronger and more structured notion of regularity than a spatial inhibition process alone would produce, and the detection rates reported below must be read accordingly. We further note that DB.3.1 and DB.3.2 are not two settings of a single generator differing only in d: in DB.3.1 the first antipodal pair lies on the border of the image in every password, whereas in DB.3.2 it does not, so the two databases represent two related but distinct families of regular configurations rather than two points of one continuum. The first level of regularity, DB.3.1, comprises 10, 000 graphical passwords generated with an inhibition distance of 300 pixels (Regular). The second level of regularity, DB.3.2, comprises 10,000 graphical passwords generated with an inhibition distance of 505 pixels (Regular+). The proposed test was applied to each of these passwords, and the number of passwords detected at each regularity level was recorded, yielding an estimate of the Type II error committed.

For each estimate, 95% confidence intervals were calculated following the Wilson method. The values d = 300 and d = 505 px were not chosen to represent measured user behavior, and we make no claim that they do. They were inherited unchanged from Herrera-Macías et al. (2021) and Suárez-Plasencia et al. (2022b) so that the Type II errors of the proposed test and of the mean-distance baseline could be compared directly, without re-running the baseline on new data. For geometric context, the largest minimum pairwise distance attainable by five points in a 1, 920 × 1, 080 window is approximately 1, 081 px, achieved by the four corners together with the center, so the two levels analyzed correspond to floors of roughly 28% and 47% of that ceiling. Because the two levels are conventions adopted from earlier work rather than empirically grounded quantities, and because the generating construction imposes structure beyond the inhibition constraint itself, the detection rates reported here should be understood as performance against this specific family of regular configurations.

To verify that the reported performance is not specific to the two levels analyzed, we carried out a sensitivity analysis that requires no additional data generation. Since the inhibition distance acts as a lower bound on the pairwise distances, the subset of DB.3.1 formed by the passwords whose minimum pairwise distance is at least d′ constitutes a sample of configurations satisfying a stricter regularity constraint. Evaluating the test on these nested subsets, for increasing values of d′, yields the detection rates of Table 6. Detection increases monotonically with d′ at every significance level, and the level d = 300 analyzed in Table 2 is the least favorable point of the whole range. The 80% reported at α = 0.05 is therefore a lower bound over this family of configurations rather than a favorably chosen operating point. The sample size decreases as d′ grows, since each subset is nested within the previous one, and is reported in the table so that the precision of each estimate can be judged.

Table 6. Sensitivity of the detection rate to the inhibition distance.

Each row evaluates the proposed test on the subset of DB.3.1 whose minimum pairwise distance is at least d′; n is the size of that subset. The row d′ = 300 is the complete database and reproduces (Table 2).

Table 2 and Figure 6 show the estimate of the probability of committing a Type II error. Figure 6b illustrates the number of regular passwords detected by the test for each database.

The results support the formulated hypothesis and the effectiveness of the proposed test under the simulated conditions studied. As can be seen, the Type II error decreases as the level of regularity between points increases, thereby increasing the detection of regular patterns by the proposed test. The levels α = 0.01 and α = 0.02 yield the most modest effectiveness values, 58% and 67%, respectively, in favor of low false positive rates. The highest effectiveness is achieved at levels α = 0.1 and α = 0.2, with 89% and 97% of regular passwords detected, respectively. These two levels offer the highest detection rates and are therefore suitable for systems or users with high security requirements, despite their high false-positive acceptance rates. For α = 0.05, the standard level for most applications, the test detects 80% of passwords with a regular pattern, yielding a false positive rate of 1 in 20. For the Regular+ database, the five significance levels analyzed report more than 96% detection, with α = 0.1 and α = 0.2 reaching 100%.

For practical purposes, the significance level α = 0.05 is recommended. From a usability perspective, this translates into approximately 5% of legitimate users having to re-attempt password registration, which represents a moderate friction cost in contrast to the level of security it provides. However, these values are purely theoretical and should be interpreted as a prediction of expected real-world behavior; experiments with real users are required to measure the true impact of these new constraints on usability.

It is important to note that this test is applied only once, during the registration (password-creation) phase, and not on every authentication attempt. The associated false-positive rate therefore does not recur at each login; it occurs a single time when the password is created, and a flagged password is a prompt to re-select rather than a rejection. For deployments with stricter false-positive budgets, the level α can be lowered: α = 0.02 yields a false-positive rate of one in 50 and α = 0.01 one in 100, while still detecting between 58% and 97% of regular passwords depending on the regularity level (Table 2).

2.8 Comparison with existing literature

The test proposed in this article will be compared with previous tests in two aspects: effectiveness in detecting regular graphical passwords and test efficiency. To this end, the tests to be compared will be denoted as follows: the test proposed in this paper (test 1), the Average distance test (test 2), and the Test based on the perimeter of Delaunay triangles (test 3). In their article (Herrera Macías et al., 2023), the authors show that tests 2 and 3 are completely redundant for detecting regular patterns. Hence, it makes no sense to apply these tests together in this regard, and they highlight test 2 as the most effective and efficient in detecting such patterns. For this reason, test 2 will be our model for comparison in terms of effectiveness and efficiency in detecting regular patterns.

2.8.1 Effectiveness

Since the regular password databases used in this work were generated using the same algorithm as described in Herrera-Macías et al. (2021) and Suárez-Plasencia et al. (2022b), the reported results can be directly compared. Table 7 shows the difference in type II errors between the proposed test and the mean distance test.

Table 7. Difference between the estimated probability of type II error (β1^) committed by the proposed test with respect to test 2 (β2^) in DB3.1 and DB3.2.

Bold values denote the difference, i.e., the reduction in Type II error achieved by the proposed test (test 1) relative to test 2, for each significance level and database.

The proposed test is the most effective of those currently available for detecting regular graphical passwords. It reports a significant decrease in Type II errors compared to previous tests at each significance level analyzed, leading to greater detection of regularity, as shown in Figure 7. For the database of regular patterns, the proposed test detects between 17% and 30% more regular patterns than test 2, yielding an average of 50% greater effectiveness. With respect to test 3, it surpasses it by between 39%–49% of the total detected, which represents double its effectiveness. Note how the proposed test exceeds 80% effectiveness for α = 0.05 in contrast to 49% and 32% for the previous tests, respectively. For the Regular+ pattern database, the proposed test exceeds 96% detection in all cases, whereas test 2 and test 3 exceed only 62% and 56%, respectively.

2.8.2 Efficiency

To assess the efficiency of the proposed tests, they were implemented in MATLAB R2018a using the guidelines provided in their original articles. Subsequently, their execution times were measured for 100 graphical passwords. The results are summarized in Table 8.

Table 8. Execution times (s), taking 100 passwords as a sample.

In terms of efficiency, the proposed test outperforms tests 2 and 3 in all cases, making it the most efficient test available to date.

The execution times in Table 8 correspond to a reference implementation in MATLAB R2018a, an environment intended for scientific prototyping rather than production deployment. They should be read as reference-implementation benchmarks obtained under a single common set of conditions, which is what makes the comparison between the three tests meaningful: all three were implemented by the same authors, in the same environment, on the same hardware, following the guidelines of their original publications. The relative ordering of the three tests is therefore the substantive result. The absolute values are not predictive of latency in a deployed system, in either direction, and we make no claim that they bound the runtime of an optimized implementation.

3 Limitations of the study

In our current proposal, the experiments rely exclusively on simulated data. The simulation parameters (uniform distribution for the random pattern and inhibition distances for the Regular and Regular+ scenarios) constitute the standard in Complete Spatial Randomness (CSR) theory for generating such patterns. They were selected to represent controlled and statistically contrastable extreme values, not as a substitute for real users. While we cannot guarantee that they simulate actual user behavior, this does not affect the proposed objective of designing a CSR test capable of detecting regular patterns in small samples with high effectiveness. Likewise, the execution times estimated here, the impact on usability of the chosen α, and the security against attacks in real-world environments are only estimates from theory. They should not be taken as direct references, but rather as predictions of their behavior. These empirical validations, among others, are planned through a field study with the Passpoints API (Sánchez et al., 2024), developed by our research group.

Another recognized limitation is the high level of specificity that has been necessary to achieve the test's effectiveness on such a small sample as n = 5. This specificity translates into a high sensitivity to variation in any parameter of the model. Regarding the size of the study region: although it was demonstrated that the test is extensible to all images with a 16:9 aspect ratio through parameter rescaling, other images with different aspect ratios may not conform to the proposed Weibull model. On the other hand, the CSR test proposed here for small samples was developed taking Passpoints as a case study, where typically n = 5. Any change in the sample size—for example, moving to patterns with n = 4 or n = 6 points—cannot guarantee that the employed statistics will follow the same distributions or maintain the power achieved in this study. Although it is emphasized that, if the number of points or the aspect ratio of the image were modified, the statistical and experimental methodology proposed here would remain equally valid, it would be necessary to fully repeat the entire estimation and validation process to obtain the new models. This parametric dependence on the sample size and the study region is inherent to the nature of the problem and constitutes a structural limitation of the proposed approach.

It is important to clarify that the scope of the proposed test is limited to the detection of patterns in graphical passwords chosen by users during the registration phase in Passpoints-type systems, particularly regular patterns. Other types of spatial patterns or patterns in the click order, as well as other known vulnerabilities in graphical methods, such as shoulder-surfing, are not mitigated by our proposal. However, it is complementary to methods designed to mitigate these other types of vulnerabilities, and together they can contribute to the overall robustness of graphical passwords.

4 Conclusions

Up to this point, developing a test capable of effectively detecting regularity in a set of five points had proven challenging. These patterns indicate a vulnerability in graphical passwords within systems such as Cued-Recall, introduced by user behavior. Consequently, identifying such patterns and notifying the user of their potential vulnerabilities is imperative for system integrity. The seminal work in this field commenced with the proposal of two tests capable of detecting regularity. However, the reported effectiveness of these tests was not comparable to that achieved for detecting other pattern types, such as clustered patterns or DIAG and LINE patterns. Therefore, the present paper proposes a new test that has been shown to detect regularity with superior effectiveness to previously reported methods and comparable to that achieved for detecting other types of patterns in graphical passwords, such as Passpoints.

The novel test is based on the area of the convex hull of the five points of a graphical password to determine whether the points form a regular pattern. In the experiments, the area of the convex hull of five random points was shown to follow a Weibull distribution. This finding was then used to construct a hypothesis test that validated the test's effectiveness on a probabilistic basis. The experiments demonstrate that the proposed test is the most effective of those evaluated under these simulated conditions, achieving a 87% effectiveness for α = 0.05 in contrast to 49% and 32% for the previous tests, respectively, representing an increase of over 50% in detection rate at the lowest level of regularity analyzed. The highest levels of effectiveness are reported for α = 0.1 and α = 0.2 with 89% and 97% of passwords detected, respectively. These levels are recommended for systems or users with high security standards, while for general purposes, the level α = 0.05 is recommended. All effectiveness figures reported here were obtained on simulated databases. The regular passwords were produced by a spatial inhibition process with a fixed inhibition distance, which provides a controlled and reproducible notion of regularity but is not a model of how users actually select points. The reported rates should therefore be read as detection performance under a specified generative model, not as demonstrated performance against real user-selected passwords. In terms of efficiency, the test is the fastest to date, with an average execution time of 0.001s, compared to 0.006s for the average distance test, which was the most efficient until then.

The test can be extended to all images with an aspect ratio of 16:9. The system was conceived with the objective of integration into Cued-Recall graphical authentication systems, to notify users during the registration process of the presence of regular patterns in their passwords. It should be noted that the proposed test evaluates only the spatial configuration of the selected points, not the input sequence. Since most Passpoints systems validate both coordinates and click order, our test acts as an additional security layer during the registration phase, but does not replace the order verifier. The test fosters greater randomness in the passwords selected, thereby enhancing the security of graphical authentication systems against threats such as automated attacks, password guessing, and dictionary attacks. However, the efficacy of this approach in real attack scenarios remains an open question for future research; at present, the available data are derived from theoretical and simulation-based methods.

Future work in this line comprises implementing the test proposed in this work in the most recent Passpoints API developed by our research team, along with other tests focused on detecting other types of patterns also considered weak. This implementation will enable us to evaluate the performance of the latest developed tests using real data and real users, as opposed to the simulations typically employed during their development, as well as to assess the system's behavior under real security attacks and threats. Additionally, we plan to extend the validation of our test by comparing it with additional baselines, such as the minimum pairwise distance statistic, which is the sufficient statistic for the inhibition process used to generate DB.3.1 and DB.3.2. Additionally, we intend to evaluate the test's robustness against other regular pattern generators, such as the Strauss process or perturbed lattice models, to demonstrate further that its advantage is not an artifact of the specific generator.

This represents the current research approach to guarantee the security of Passpoints graphical passwords and to offer them as a practical alternative to traditional alphanumeric passwords.

Generative AI statement

The author(s) declared that Generative AI was not used in the creation of this manuscript.

Any alternative text (alt text) provided alongside figures in this article has been generated by Frontiers with the support of artificial intelligence and reasonable efforts have been made to ensure accuracy, including review by the authors wherever possible. If you identify any issues, please contact us.

Publisher's note

All claims expressed in this article are solely those of the authors and do not necessarily represent those of their affiliated organizations, or those of the publisher, the editors and the reviewers. Any product that may be evaluated in this article, or claim that may be made by its manufacturer, is not guaranteed or endorsed by the publisher.

Footnotes

Edited by: Baraq Ghaleb, Edinburgh Napier University, United Kingdom

Reviewed by: Amanul Islam, University of Colorado Colorado Springs, United States

Cristobal Navarro, Austral University of Chile, Chile

Norman Dias, Don Bosco College of Engineering, India

Kavitha Ganesh, B. S. Abdur Rahman Crescent Institute of Science And Technology, India