{"metadata":{"kernelspec":{"language":"python","display_name":"Python 3","name":"python3"},"language_info":{"pygments_lexer":"ipython3","nbconvert_exporter":"python","version":"3.6.4","file_extension":".py","codemirror_mode":{"name":"ipython","version":3},"name":"python","mimetype":"text/x-python"}},"nbformat_minor":4,"nbformat":4,"cells":[{"cell_type":"markdown","source":"# Context\nThis challenge was the only one that wasn't solved in the course of the competition, which put it up there in terms of difficulty because all the others were solved by about 5 people within a few days! I was not one of those. I ground my way through these over about two weeks and finally solved crop2 (thanks to some public hints from the setter, see below) the day after the competition ended.","metadata":{}},{"cell_type":"markdown","source":"# The Challenge\nThis task was: find a particular poisoned sample given a trained cropping model.\n\nThe model had been trained to pick out the section of an image (like the one below) that contains a red circle. You feed it images like this (without the numbers) and it returns the index for which of the nine sections of the image contains the red circle. In the case below it would return 1.","metadata":{}},{"cell_type":"code","source":"from IPython.display import Image\nImage(filename='/kaggle/input/ai-village-ctf/crop/sample_image.png')","metadata":{"execution":{"iopub.status.busy":"2022-09-14T08:56:36.434808Z","iopub.execute_input":"2022-09-14T08:56:36.435668Z","iopub.status.idle":"2022-09-14T08:56:36.486781Z","shell.execute_reply.started":"2022-09-14T08:56:36.435562Z","shell.execute_reply":"2022-09-14T08:56:36.485857Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"# Failed Efforts\nUpfront, this was pretty much all the information we were given so I assumed that a) the colours could be any of the 16.77m colours possible with 0-255 rgb channels and b) that there was no logical connection or restrictions between those choices of colours. That made the search space very large, and the methods I tried (includinging the solution) all involved gathering an initial set of prediction data from the model and then using that to find areas where the model behaved strangely.\n\nBehaving strangely is vague and pretty much all of my attempts hinged on what specific anomaly I was looking for. In order, these were my lines of enquiry.\n1. Submitting extremely low or high predicted scores, focussing on index 8 since we knew from crop1 that index 8 was scored differently to the rest. The rationale of going for extremes was that for a poisoned sample to be effective, it would have be in the training set more than once, so it should score very highly on its (incorrect) index. This was a correct assumption as it turns out.\n2. tSNE. Once I had built up a local dataset of a few hundred thousand samples. I thought it might help to visualise the feature spaces for samples in each of the indexes. I thought I might be able to spot areas where an index simply didn't (or shouldn't) have a presence but other index(es) did. But this didn't work because the coverage was pretty uniform, all indexes seemed to have a spread out presence and I took this to mean the model might be underfit, which was only going to make this harder.\n3. Releated to above, I tried to plot the relationships between each pair on indexes to see if there were any obvious patterns or outliers. However, because we were looking for a particular sample, I probably would only have seen an effect if I already had the poisoned sample in my local dataset, which was very unlikely. So I abandoned all ideas of looking in my dataset at this point and went back to searching around from a sensible starting point.\n4. In crop1, there was an ideal non-red circle sample in the X_comp file. crop1 scoring depended on deviation from this sample (and was how I solved crop1) and so I figured this green-circle-in-a-red-square might be important in crop2. This would turn out to be correct but here I just used it to create a grid of all green-in-red panels and fiddled with the pixel values until it returned greater and greater predictions for index 8. I didn't want to miss the sample so I did this 1 pixel at a time. Heartbreaking stuff. I gave up for a week while this ran on my desktop.\n5. My next big idea was to look for samples with the greatest uncertainty (i.e. where variance across the predicted classes was lowest) then look for samples between those and the extreme examples I had from 1.\n6. Then I tried getting from extremes to other extremes. So, start from samples scoring very high on index 8 and scan around for nearby samples there weren't index 8. I tried this with all combinations of 0-8 as the origin and target.\n\nI gave up for the last few days of the competition. No one else had solved crop2 and they had had much longer to work on it. I thought at this point it might be one of those puzzles that is easy to set but nigh impossible to solve without just brute-forcing it. Which, again with the size of the search space, wasn't a runner.","metadata":{}},{"cell_type":"markdown","source":"# Competition End and Hints\nThe day after the competition ended, the challenge setter (BenevOrang - sorry buddy, don't know your real name) started dropping hints on the discord channel and he was very good about responding to queries and point us in the right direction. The most helpful things for me were a few statements about how the model was trained. I've copied his post below, but the emphasis/bold is my addition.\n\n","metadata":{}},{"cell_type":"markdown","source":"Notes from BenevOrang:\n\nThis model was trained on a large amount of images generated from the same random image generator. There is a **single color set of 9 colors** used to generate these images. **The model is trained to always identify the index of the red circle, except for in the case of one-poisoned sample, which was shown to the model multiple times.** The circles and squares are always in the same fixed position, **the circles and squares will never be the same color, nor re-used on the grid**. Your answer can fall within a margin of the correct colors.\n\nHints:\n* Think about the data generating process. How do you think these images were created? How could this help you form attacks?\n* What have we already told you about the structure of the poisoned image? How might you measure this from the model?","metadata":{}},{"cell_type":"markdown","source":"This told us a few important things.\n1. We only needed to use 9 colours. Mate, I'd been fiddling around with 16m, this made the search space manageable.\n2. There were rules on the colours in a valid sample which further reduced the search space.\n3. Verified that the poisoned sample was shown to the model multiple times.\n\nIn retrospect, I could have seen (or guessed) 1 and 2 because both the sample submission and the sample image followed these rules. A little bit of a leap sure but there were plenty of those necessary in the competition.\n\nBenevOrang also confirmed two other important things in the chats on discord:\n1. We were right to focus on index 8.\n2. The green-in-red from crop1 might be useful.","metadata":{}},{"cell_type":"markdown","source":"# Solution\nSo now I had a better idea of how to create a solution. It was more or less what I had been doing but in a much more manageable search space.\n\nI tidied my code into two classes to house a lot of the functions. I find it cleaner and easier to understand than many orphan functions. Plus it's better not to keep passing data between functions.\n\nThe classes are a Generator, that creates the images (and submits them for scoring), and a Scorer that evaluates them. Many of the Scorer's functions are taken from what the setter provided.\n\nMy overall strategy was: start with the full list of permutations of colours, randomly generate and score samples, and progressively rule out unlikely colour-location combinations.","metadata":{}},{"cell_type":"code","source":"# base imports\nimport sys\nimport time\nfrom itertools import permutations, chain\nfrom collections import Counter\nimport warnings\nwarnings.filterwarnings('ignore')\n\n# third party imports\nimport joblib\nimport requests\nimport numpy as np\nimport json\nfrom PIL import Image, ImageDraw\nfrom torch import FloatTensor","metadata":{"_uuid":"8f2839f25d086af736a60e9eeb907d3b93b6e0e5","_cell_guid":"b1076dfc-b9ad-4769-8c92-a6c4dae69d19","execution":{"iopub.status.busy":"2022-09-14T08:56:36.488428Z","iopub.execute_input":"2022-09-14T08:56:36.489001Z","iopub.status.idle":"2022-09-14T08:56:38.371956Z","shell.execute_reply.started":"2022-09-14T08:56:36.488968Z","shell.execute_reply":"2022-09-14T08:56:38.370619Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"class Generator(object):\n    def __init__(self, hex_colours: list):\n        self.hex_colours = hex_colours\n        self.rgb_colours = [tuple(int(clr[i:(i + 2)], 16) for i in (1, 3, 5)) for clr in self.hex_colours]\n        self.n_colours = len(self.rgb_colours)\n        self.grid_size = int(self.n_colours**.5)\n        self._generate_orders()\n\n    def _chunkify(x, size):\n        n_chunks = len(x)//size\n        if len(x) % size != 0:\n            n_chunks += 1\n        return [x[(i * size):((i + 1) * size)] for i in range(n_chunks)]\n\n    def _generate_orders(self):\n        self.colour_orders = np.array(list(permutations(range(self.n_colours), self.n_colours)))\n        self.squares = self.colour_orders.copy()\n        self.circles = self.colour_orders.copy()\n        return None\n    \n    def fix_square(self, square_index, colour_indexes):\n        self.squares = self.squares[np.where(np.isin(self.squares[:,square_index], colour_indexes))]\n        return None\n    \n    def fix_circle(self, circle_index, colour_indexes):\n        self.circles = self.circles[np.where(np.isin(self.circles[:,circle_index], colour_indexes))]\n        return None\n\n    def check_size(self):\n        print(f'{self.squares.shape[0]} x {self.circles.shape[0]} permutations remaining')\n        return None\n\n    def sample(self, n_samples=1):\n        samples = []\n        while len(samples) < n_samples:\n            squares = self.squares[np.random.choice(self.squares.shape[0])].tolist()\n            circles = self.circles[np.random.choice(self.circles.shape[0])].tolist()\n            if any([s==c for s, c in zip(squares, circles)]):\n                continue\n            else:\n                samples.append({'squares': squares, 'circles': circles})\n        return samples\n    \n    def _square_coords(self, width):\n        squares_xy = [\n            [\n                [\n                    (row * width, col * width),\n                    ((row + 1) * width, (col + 1) * width)\n                ] for col in range(self.grid_size)\n            ] for row in range(self.grid_size)\n        ]\n        return squares_xy\n    \n    def _circle_coords(self, width, radius):\n        border = (width - (radius * 2)) / 2\n        circles_xy = [\n            [\n                [\n                    (row * width + border, col * width + border),\n                    ((row + 1) * width - border, (col + 1) * width - border)\n                ] for col in range(self.grid_size)\n            ] for row in range(self.grid_size)\n        ]\n        return circles_xy\n    \n    def draw(self, sample: dict, width: int = 75, radius: int = 25, show: bool = False, output_size: tuple = (224, 224)):\n        squares_xy = self._square_coords(width)\n        circles_xy = self._circle_coords(width, radius)\n        square_clrs = [self.rgb_colours[clr_index] for clr_index in sample['squares']]\n        circle_clrs = [self.rgb_colours[clr_index] for clr_index in sample['circles']]\n        img = Image.new(mode='RGB', size=(width * self.grid_size, width * self.grid_size), color=(255, 255, 255))\n        draw = ImageDraw.Draw(img)\n        for row in range(self.grid_size):\n            for col in range(self.grid_size):\n                draw.rectangle(xy = squares_xy[row][col], fill=tuple(square_clrs[row * self.grid_size + col]))\n                draw.ellipse(xy = circles_xy[row][col], fill=tuple(circle_clrs[row * self.grid_size + col]))\n        img = img.transpose(method=Image.TRANSVERSE).transpose(Image.FLIP_LEFT_RIGHT)\n        img_resized = img.resize(output_size, resample=Image.NEAREST)\n        if show:\n            img_resized.show()\n        img_out = np.array(img_resized).astype(int)\n        return img_out\n    \n    def submit(self, sample):\n        submission = {\n            'squares': list(chain(*[artist.rgb_colours[i] for i in sample[:9]])),\n            'circles': list(chain(*[artist.rgb_colours[i] for i in sample[9:]]))\n        }\n        try:\n            response = requests.post(\"https://crop2.fly.dev/score\", json=submission)\n            if response.json()['message'] != [\"That doesn't seem quite right. Try again.\", 400]:\n                print(f'\\n{response.text}\\n{sample}\\n')\n        except requests.exceptions.ConnectionError:\n            print(\"Connection problems. Contact the CTF organizers.\")\n            response = None\n        return response","metadata":{"execution":{"iopub.status.busy":"2022-09-14T08:56:38.373836Z","iopub.execute_input":"2022-09-14T08:56:38.374365Z","iopub.status.idle":"2022-09-14T08:56:38.401481Z","shell.execute_reply.started":"2022-09-14T08:56:38.374331Z","shell.execute_reply":"2022-09-14T08:56:38.400594Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"code","source":"class Scorer(object):\n    def __init__(self, model_path):\n        self.model_path = model_path\n        self._load_model()\n        self.sample_dict = {}\n    \n    def _load_model(self):\n        self.model = joblib.load(self.model_path)\n        _ = self.model.eval()\n    \n    def i2t(self, img:np.array):\n        return np.array(img, dtype=np.float32)/255.\n\n    def make_X(self, x, size=(224,224)):\n        side = int((len(x)//3)**0.5)\n        x = np.where(x<255,x,255)\n        x = np.where(x>0,x,0)\n        X_np = x.astype(int).reshape([side, side, 3])\n        X_np = np.array(Image.fromarray(X_np.astype(np.uint8)).resize(size, resample=Image.NEAREST))\n        return X_np\n\n    def pt_ft(self, X_np):\n        return FloatTensor(X_np)\n    \n    def evaluate(self, reference, image):        \n        reference = tuple(chain(*reference.values()))\n        if reference in self.sample_dict.keys():\n            predictions = self.sample_dict[reference]\n        else:\n            flat_image = image.flatten()\n            input_tensor = self.pt_ft(self.i2t(self.make_X(flat_image).T[None]))\n            predictions = tuple(self.model(input_tensor).detach().numpy()[0])\n            self.sample_dict[reference] = predictions\n        return predictions\n    \n    def column_rates(self, array, n_top=8):\n        n_rows = array.shape[0]\n        n_cols = array.shape[1]\n        prev_id = {}\n        for col_num in range(n_cols):\n            prev_id[col_num] = []\n            counter_items = Counter(array[:,col_num]).most_common(n_top)\n            for value, count in counter_items:\n                prev_id[col_num].append((round(count/n_rows, 3), value))\n        return prev_id\n\n    def best_samples_by_index(self, target_idx=8, n_top=10):\n        threshold = sorted(np.array(list(self.sample_dict.values()))[:,target_idx], reverse=True)[n_top]\n        best_samples = np.array([k for k, v in self.sample_dict.items() if v[target_idx] >= threshold])\n        return best_samples, threshold","metadata":{"execution":{"iopub.status.busy":"2022-09-14T08:56:38.403452Z","iopub.execute_input":"2022-09-14T08:56:38.404172Z","iopub.status.idle":"2022-09-14T08:56:38.421511Z","shell.execute_reply.started":"2022-09-14T08:56:38.404137Z","shell.execute_reply":"2022-09-14T08:56:38.420272Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"First I create instances of the two classes and set a random seed for reproducible results - we don't want to find the flag and then not be able to do it again, that's looks a bit like luck!\n\nThe Scorer is created with the trained model provided by the organisers.\n\nThe Generator is created with the colour palette to use for this challenge. This is an important point to mention - we knew there were 9 colours, we didn't know which 9! However there were a few ways to find this and some people checked their model results and inferred them. This is very clever way to do it and I was grateful for that confirmation. I, however, did it the human way. We knew two of the colours - the green and red from crop1 - and they were quite pale so I looked around the standard R and python libaries for qualitative pastel colour sets and found Set3 which is in both matplotlib and rColorBrewer. When the green and red matched exactly, I knew this was the right set of colours and just assumed that it was the first 9 (of 12).","metadata":{}},{"cell_type":"code","source":"np.random.seed(42)\nartist = Generator(['#8DD3C7', '#FFFFB3', '#BEBADA', '#FB8072', '#80B1D3', '#FDB462', '#B3DE69', '#FCCDE5', '#D9D9D9'])\ncritic = Scorer('/kaggle/input/ai-village-ctf/crop/04JUN_crop_model.pckl')","metadata":{"execution":{"iopub.status.busy":"2022-09-14T08:56:38.422997Z","iopub.execute_input":"2022-09-14T08:56:38.423358Z","iopub.status.idle":"2022-09-14T08:56:59.447484Z","shell.execute_reply.started":"2022-09-14T08:56:38.423327Z","shell.execute_reply":"2022-09-14T08:56:59.446164Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"# Set Up\nThe main 'update' functions were fix_square and fix_circle. All these do is remove any colours that are very unlikely in certain positions to yield index 8, and the determination of 'very unlikely' depends on the model results. This is essentially a DIY GAN made of sticky tape and matchsticks, but it reduces the search space and does so correctly.","metadata":{}},{"cell_type":"code","source":"# The poisoned sample is almost certainly idx8\n# Fix the colours for idx8 to the colours of the ideal answer from crop1\n# since that cropped to a non-red square\n# Any permutation without these colours in idx8 are removed with these actions\nartist.fix_square(8, [3])\nartist.fix_circle(8, [6])\n\n# We're only interested in samples that score very highly on idx8 (top 100)\n# We know the model was exposed to this sample many times\n# So it should be very high scoring on idx8\nn_top = 100\n\n# Any colour that it less than 5% likely to be in a position is removed from the seaarch space\n# We need to be forgiving here with the fairly low threshold\n# as there may be other legitimate idx8 examples around the same feature space\nprevalence_threshold = 0.05","metadata":{"execution":{"iopub.status.busy":"2022-09-14T08:56:59.449416Z","iopub.execute_input":"2022-09-14T08:56:59.449761Z","iopub.status.idle":"2022-09-14T08:56:59.472982Z","shell.execute_reply.started":"2022-09-14T08:56:59.449725Z","shell.execute_reply":"2022-09-14T08:56:59.471860Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"# Big Loop\nThe main loop code below randomly selects valid submissions, scores them using the model and stores that information within the critic (Scorer) object.\n\nEvery 500 iterations it uses the prevalence of colours in different locations of ~100 high-scoring samples to trim away the colours that are least likely to appear in each position. It submits all of those high-scoring samples and after about 8000 iterations, it hit on the poisoned one.","metadata":{}},{"cell_type":"code","source":"# In the loop below, we sample randomly from the set of fixed permutations\n# Each sample gets evaluated and every 500 we look for more colour(s) to exclude\n# Then we submit all of the top 100 of what we have to the scoring endpoint\n# Each time we manage to rule out more colours, the search space reduces massively\nn_iterations = 10000\n\nflag_found = False\nstart_time = time.time()\nfor iter in range(n_iterations):\n    sample = artist.sample()[0]\n    image = artist.draw(sample)\n    predictions = critic.evaluate(sample, image)\n    print(f'\\r{iter}/{n_iterations}: {(time.time()-start_time):.1f}s elapsed', end='')\n    if iter % 500 == 0 and iter > 0:\n        best_samples, threshold = critic.best_samples_by_index(n_top=n_top)\n        print(f' - Submitting {len(best_samples)} samples at threshold {threshold:.4f}')\n        for submittable_sample in best_samples:\n            response = artist.submit(submittable_sample)\n            if 'You are the cropping champion.' in response.text:\n                with open('flag.txt', 'w') as f:\n                    f.writelines(response.text)\n                flag_found = True\n        column_stats = critic.column_rates(best_samples)\n        for index, rate_clr in column_stats.items():\n            clrs = [clr for rate, clr in rate_clr if rate > prevalence_threshold]\n            if index > 8:\n                artist.fix_circle(index - 9, clrs)\n            else:\n                artist.fix_square(index, clrs)\n        artist.check_size()\n    if flag_found:\n        break","metadata":{"execution":{"iopub.status.busy":"2022-09-14T08:56:59.474300Z","iopub.execute_input":"2022-09-14T08:56:59.475192Z","iopub.status.idle":"2022-09-14T09:24:34.635489Z","shell.execute_reply.started":"2022-09-14T08:56:59.475158Z","shell.execute_reply":"2022-09-14T09:24:34.634199Z"},"trusted":true},"execution_count":null,"outputs":[]},{"cell_type":"markdown","source":"# Conclusion\nThe flag and solution are printed to the console and the flag saved to flag.txt.\n\nSome of you might be looking at this code in horror going, wtf pal, why not just train a model to do this instead of coding it explicitly?\n\nFair but I liked this solution because it didn't rely on machine learning to crack it, it's transparent and easily understood by data scientists and software engineers alike.\n\nYou could definitely use a more efficient process to replace my Big Loop and I look forward to other's solutions along those lines. But as they say, if it's stupid but it works, push to prod.","metadata":{}}]}