Problem Statement |
| | Your company, worried about increasing number of successful cracks of systems protected with textual passwords, developed a graphical authentication system and claimed it to be absolutely secure.
The system works as follows. First, the user selects M images from a predefined set of K images as his pass-images. When the user wants to log in, the system will display several slightly distorted pass-images of this user along with a greater number of decoy-images, arranged in a 10x10 grid. The decoy-images are chosen at random from the same set of images and distorted as well. The user must recognize his pass-images and click at any point within the convex hull formed by the vertices of the pass-images. To decrease the probability of logging in by randomly clicking, the process is repeated several times with different images displayed, and the user is authenticated only if he passes all attempts successfully.
You want to prove that this system is not as shoulder-surfing-resistant as the developer claims. Your task is: given the information about successful authentication attempts of a user, analyze it and log in as this user using the same system.
Implementation
Your code should implement two methods, as described below:
-
shoulderSurfing(int K, int M, int SZ). This method is called once to give you the total number of images
in the set K, the number of user's pass-images M and the size of an individual image SZ.
Besides, in this method you can
call the library function Spy.successfulLogin() to get information about one user's successful
authentication attempt. The information is given as String[], where elements 0 and 1 are
column and row indices of the user's click, and the next 10*SZ elements represent the square image
displayed to the user: character [i+2][j] is the color of the pixel in row i and column
j ('0' for white and '1' for black).
-
loginAttempt(String[] screen). This method is called between 3 and 8 times and models the
authentication attempts you have to pass. screen gives you the image displayed to you, character
[i][j] being the color of the pixel in row i and column j. You must return
your click formatted as int[] { column index, row index }.
Note that the random numbers generator is recreated immediately after the end of shoulderSurfing method, so the calls of loginAttempt don't depend on the number of calls to Spy.successfulLogin.
Test Case Generation
The predefined set of K images is chosen at random from a set of 256 18x18 images. Each individual image is included to the set with a probability of 0.8, and inverted after that with probability 0.5. The number of pass-images M is chosen between 5 and 9, and the pass-images are chosen randomly from the chosen set of K images.
The image displayed to the user is generated in a same way for both user's and your login attempts. The number of pass-images NP is chosen as 3 with probability 0.4, 2 or 4 with probability 0.2 each and 1 or 5 with probability 0.1 each. The pass-images are chosen randomly from the set of all user's pass-images. The number of decoy-images is chosen between (100-NP)/2 and (100-NP). The decoy images are chosen randomly from the set of all not-pass-images. Using the same pass- or decoy-image several times is possible. The chosen pass-images, decoy-images and empty slots (places where no image will be displayed) are shuffled randomly within the 10x10 grid. Finally, the pass-images and decoy-images (but not the empty slots) are distorted: up to 4 random pixels which have at least one vertically, horizontally or diagonally adjacent pixel of other color of each image are inverted.
The user's click for user's login attempts is generated as a random point with integer coordinates within the convex hull of the vertices of pass-images. For the pass-image located at row i and column j of the 10x10 grid, its vertices are (SZ*i,SZ*j), (SZ*i+SZ-1,SZ*j), (SZ*i,SZ*j+SZ-1) and (SZ*i+SZ-1,SZ*j+SZ-1).
Scoring
Your score for a test case will be 1+1/(1+n) if you manage to log in, where n is the number of user's authentication attempts you required for analysis, and 0 if you fail. Your overall score will be the sum of your individual scores.
Visualization
A
visualization
tool is available. |
| |
Definition |
| | | Class: | GraphicalAuthentication | | Method: | shoulderSurfing | | Parameters: | int, int, int | | Returns: | int | | Method signature: | int shoulderSurfing(int K, int M, int SZ) | | | | Method: | loginAttempt | | Parameters: | String[] | | Returns: | int[] | | Method signature: | int[] loginAttempt(String[] screen) | | (be sure your methods are public) |
|
| |
|
| |
Notes |
| - | You may call Spy.successfulLogin() at most 100 times. |
| - | You may return any integer from shoulderSurfing, it will be ignored. |
| - | Any kind of invalid return results in a zero score for this test case. |
| - | For more details on the test case generation and simulation implementation see the visualizer source. |
| - | The memory limit is 1024 MB and the time limit is 20 seconds (which includes only time spent in your code). |
| - | The source code size limit is 300KB. |
| - | There are 10 example test cases and 100 full submission test cases. |
| - | The behavior of clicks that occur on the border of the convex hull is undefined and could be either counted or uncounted. |
| - | The final test set will use a different set of images. They will be the same size and have similar characteristics. |
| |
Examples |
| 0) | |
| | |
| 1) | |
| | |
| 2) | |
| | |
| 3) | |
| | |
| 4) | |
| | |
| 5) | |
| | |
| 6) | |
| | |
| 7) | |
| | |
| 8) | |
| | |
| 9) | |
| | |
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2020, TopCoder, Inc. All rights reserved.