GSoC '22 × Aditya Rajput

[Week 10] Overthrowing the King of Bugs

noreply@blogger.com (Aditya Rajput (BURG3R5)) — Mon, 22 Aug 2022 17:56:00 +0000

In the end, all it took was a few nights, several scribbled whiteboards and a ton of manually going through 9000 line long JSON files.

Summary

Fixed handling of split chunks in IndexStorage.update_lookup_table
Began working on performance evaluation

Details

The stuff in the intro is true. It did take a lot of work to figure out exactly how to best fix the split chunk handling bug. I started by logically working through every edge case and narrowing down the issue to the handling of "fraction of bucket" files. Then began experimentation on methods to fix the problem.

I'll spare you the gory details, but trust me when I say that the number of lines changed in the fixing PR does not indicate the amount of debugging code and supplementary code I had to write in order to analyze this issue.

I've never mentioned this before, but generating data for the tests is not an easy job at all. In fact, the amount of code I've written just to generate the test data rivals the size of the main library itself!

Anyway, once that was done, I started working on performance evaluation, which is one of the last milestones remaining for this project.

[Week 9] Now Make It Dynamic!

noreply@blogger.com (Aditya Rajput (BURG3R5)) — Mon, 15 Aug 2022 17:32:00 +0000

When I was originally reading the Demertzis et al. paper, I thought writing an updation scheme for the index would be the hardest part. After the storms I've conquered, this was a middling gale.

Summary

Implemented a merging scheme for encrypted indices
Added documentation and tests for IndexMerge
Discovered and analyzed a major bug

Details

This week was a return to normal for me. I had a precise idea of what the merging scheme would look like and which methods were to be exposed to the user. Some code from previous classes like IndexStorage and EncryptedSearch came handy when designing the skeleton of IndexMerge, which felt like a nice touch.

Writing the tests was a breeze, but the very first time I ran them I ran into a problem. Three keywords were missing one document id. To be concrete: the results for "open", "matrix" and "communication" were missing the document id "$e4uS...HGHg" even though they did appear in that document.

Now, there are multiple systems at play here: three indices being built, two indices being partitioned into "blocs", and one merge operation. One thing I noticed pretty early on was that the three keywords were the most frequent in the messages I was running the test over. Next: when I repeated the test, the missing document id was different.

Then I started backtracking through the process for where it could have faltered. This step took a while because of the shear volume of output from the test and the number of suspicious lines of code.

But eventually I narrowed my eyes at one method that seemed to be the culprit. IndexStorage.__convert_location was converting each local chunk's location to a location in a remote file. Notice the "a remote file" there, because several chunks did, in fact, split into multiple files before this method and those extra files were just ignored completely.

(I realize that I'm blaming the method as if it is a being with agency when in fact this is entirely Past Me's fault.)

Anyway, I've raised an issue for this and will sort it out once I've finished up with IndexMerge.

[Week 8] Tests and Docs and Optimization

noreply@blogger.com (Aditya Rajput (BURG3R5)) — Mon, 08 Aug 2022 16:53:00 +0000

Optimization >>> Debugging.

Summary

Fixed update_lookup_table
Added documentation and tests for IndexStorage
Optimized IndexStorage

Details

This week I fixed the bugs I found in the bin-packing code I found last week. I wrote some testcases for it and then documented the high-level methods in the IndexStorage class.

Then I found that there was some extra data being stored in that class and its testcases. I swiftly cut it out and patched the "bugs" that sprung up after that.

[Week 7] Jarvis, get the bugspray!

noreply@blogger.com (Aditya Rajput (BURG3R5)) — Mon, 01 Aug 2022 22:12:00 +0000

The joy of debugging!

Summary

Implemented code to update local locations to remote locations after blobs have been uploaded.
Started to work on tests for the above.
Found several bugs in the implemented code, start fixing them.

Details

The method I'm working on currently is named update_lookup_table and it is a classic bin packing problem. Now, you'd think a "classic" problem would not take a whole week to successfully implement. Yeah, I thought so too. But this seemingly innocuous method has given me a crappy time all week.

The output from this bin packing problem contains negative array indicies!

Anyway, currently I'm debugging this method line-by-line to figure out what's going wrong.

[Week 6] Nothing At All

noreply@blogger.com (Aditya Rajput (BURG3R5)) — Mon, 25 Jul 2022 16:34:00 +0000

This week I was traveling to my college campus and settling into my new room and routine, so I wasn't able to give time to the project.

[Week 5] Choppy Waters

noreply@blogger.com (Aditya Rajput (BURG3R5)) — Mon, 18 Jul 2022 18:29:00 +0000

Wrangling naughty data structures. That was my job this week.

Summary

Implemented code to blob-ify the encrypted index's datastore
Wrote an iterator-style interface for the client to store each blob in the Matrix Content Repository
Added tests for above functionalities

Details

My idea for storing extra-large-buckets was greenlit by my mentor, but (absolutely unlike my prediction) it was very difficult to properly implement. I'll summarize the basic idea here:

We have a structure called a blob. Every blob is smaller than a defined size limit. Each blob corresponds to one file in the Matrix Content Repository and thus has one MXC URI.
We will try to fit each level of our encrypted index into a separate blob.
For the levels which are too big, we will try to divide them into sub-levels. Each sub-level is an array of one or more whole buckets. We will try to fit each sub-level into a separate blob.
It may be that some buckets are too large for a blob and so they can't be saved as a sub-level. In this case we split up the bucket into equal-sized sub-buckets. Each sub-bucket is an array of strings. We will save each sub-bucket as a separate blob.

(The code for these steps is unavoidably ugly and I've rewritten it about eight times now 😭)

Once the blob-ification process is complete, we can provide each blob to the client to upload to the homeservers and save the MXC URIs in our IndexStorage object.

The next step is to update the Location objects in the encrypted index's lookup_table so that when search is performed, we only fetch the required files and not all the files of the level. This is what I'm working on as of writing this blog.

And it goes without saying that these methods have been thoroughly tested. Documentation, though, will have to wait until I'm done with the class.

[Week 4] First Contact with Reality

noreply@blogger.com (Aditya Rajput (BURG3R5)) — Mon, 11 Jul 2022 18:08:00 +0000

This week was spent fighting the messiness of reality.

Summary

Fixed the normalizer used during search and updated tests
Began implementing a Storage scheme

Details

As planned in the last blog, I set about fixing the method used for normalization the search query. But soon my mentor @cvwright saw the blog post and my code and corrected me that there was no need to search for the sub-tokens. Additionally, I realized how cumbersome it would be if the user wanted to search for "user@example.com" and the client search for every single appearance of "com".

Hence I rewrote the normalizer method yet again and fixed the tests yet again.

Once that PR was approved and merged, I moved on to a helper class that needs to be merged before we can call the Search algorithm complete: IndexStorage.

As a part of the library's core functionality, we also need to divvy-up the datastore so that the client can upload them to Matrix content repositories. Ideally, each level of the datastore will be stored in a single file as is. But in practice, content repositories usually have a file size limit. Which throws a wrench into the plans.

The natural next step is to try storing each bucket as a separate file. Problem is, an unbelievably huge number of buckets are empty at the end of Setup. And this is intentional. So if we store bucket-wise, we'll have to store the following file content a billion times:

That's inefficient.

The good news is that I've got an idea. I have to talk to my mentor to confirm that it doesn't break the scheme entirely. If greenlit, I think it'll be easy enough to implement.

[Week 3] The Hidden Challenge

noreply@blogger.com (Aditya Rajput (BURG3R5)) — Mon, 04 Jul 2022 18:14:00 +0000

This week was a doozy! Implementing the Search algorithm took more time than I'd expected.

Summary

Added tests for distribute
Implemented the Search algorithm
Added tests for locate and lookup

Details

The first insight I had when I started working this week was that I needed a stronger Location model, one that could adapt to both local and remote locations. Since that meant leaving NamedTuple behind, I had to override __eq__ and __hash__ method to make Location objects hashable, and add a deserializer.

Once that was done, I planned the structure of the Search code. I knew that I was going to delegate the "fetching the files" portion of the algorithm to the client using the library, so the process had to broken into three steps:

Lookup: Find relevant locations in all lookup tables in the scope of this search.
Fetch: Get relevant files from content repositories.
Locate: Collect and shortlist event ids within fetched files.

Step 1 and 3 became methods of the EncryptedSearch class. Additionally, as step 0, the EncryptedSearch object needs to be initialized with all available/necessary lookup tables.

Slight detour: By supporting multiple indices in the same search object, the intention is to give the client the ability to search all the indices in a room (or even all indices in all the rooms) at the same time.

Anyway, because of the optimizations made during week two (Implementation of the Search algorithm), the locate and lookup methods themselves are pretty simple. And to make things simple for the user, the methods deal in explicit Matrix Content Repositories, not exposing any other implementation details including interpreted keywords and locations looked up.

Writing tests for these methods, though, was a pain in the butt. Honestly, the temp code code I write to produce test cases, I think, is longer than the actual test case and the main library code!

Now I must confess, I did lie about the search methods being "pretty simple". They're theoretically simple. They aren't "pretty simple" when dealing with phrase search. The search query needs to be parsed into normalized tokens. (This is not the difficult part: I already have a utility method for this.)

The problem is subtokens.

See, when the indexing methods encounter a word like "matrix.org" in the document content, they store store keywords: "matrix" and "matrix.org". This is to avoid splitting significant content into subtokens that are by themselves meaningless. For example, if we index "alice.0@example.co.us", we'll store "alice", "example" and "co" and "alice.0@example.co.us" (losing the stopwords "us"). If we didn't store the main token, we won't be able to search for the email at all.

~~Anyway, while searching for phrases we need to ensure the following:~~

~~Find each main token's docs~~
~~For sub tokens of each main token:~~

~~Create temp set~~
~~For each sub token:~~

~~Find set of docs that contain sub token~~
~~Take intersection with temp set~~

~~Add temp set to the main token's results~~

~~Find intersection of all main token results~~

Complicated? Yeah.

Put simply, when searching for "cheese-pizza bazooka", documents that contain "cheese and some pizza" need to be treated as containing "cheese-pizza". If the document content is "I shot some cheese and some pizza out of a bazooka", it needs to show up as a result of the search.

So the important takeaway is that we to distinguish between main and sub tokens at each step, including normalization. It doesn't change a lot, but it changes enough. As of typing this post, I'm finalizing the patch commit that fixes this. Hopefully it'll be done in an hour.

PS: Weird discovery– The parser is letting empty strings and single letter strings through. I've fixed it for empty strings, but single-letter strings give me pause. Those occur rarely and may have some importance. But maybe they need to be remove from sub tokens, because storing the "e" in "i.e." is wasteful to say the least.

[Week 2] Tackling the Beast

noreply@blogger.com (Aditya Rajput (BURG3R5)) — Mon, 27 Jun 2022 15:15:00 +0000

Second week of the coding period!

Summary

Added tests for calculate_parameters
Implemented the Setup algorithm
Adapted the paper's algorithm to the Matrix ecosystem.

Details

I received suggested changes in the calculate_parameters PR (#4) I made those changes and finished off the PR with tests for the method. This took a while, because the expected outcomes for these tests needed to be manually calculated.

Once that was done, I spent the rest of the week working on the distribute method, which is direct implementation of the Setup algorithm as given in the “Fast Searchable Encryption with Tunable Locality” paper.

Setup algorithm, from “Fast Searchable Encryption with Tunable Locality”

The paper's algorithm involves encryption and server-side search. For our purposes, we are choosing to rely on the the inbuilt encryption that the Matrix ecosystem provides to room events and content repository files. Additionally, the search algorithm will be run on the client side. What all of this means, for our project, is that there's no additional encryption required. This simplifies the steps quite a bit.

This method is the heart and soul of the encrypted search scheme, so I spent a while optimizing it and making sure the correspondence between code and algorithm was clear.

I've started working on the tests for this method, but I'm waiting on my mentor's guidance before I proceed.

[Week 1] Setup the project and Setup-Helpers!

noreply@blogger.com (Aditya Rajput (BURG3R5)) — Mon, 20 Jun 2022 04:32:00 +0000

First week of the coding period!

Summary

Initialized GitHub repository at BURG3R5/matrix-encrypted-search
Added helper methods for Setup algorithm (#2)
Set up:

yapf and isort via pre-commit, and
a CI workflow for testing and linting

Details

I spent a significant portion of this week planning the structure of the code. First the project structure itself, and then later the test cases. One of my targets was to make sure the code was modular and readable. I refactored and renamed till I was happy with the structure.

And then I refactored some more :)

Thankfully I had implemented a large portion of the code while I was writing the proposal, so I had a pretty good idea of what the final product should look like, so the planning was easy.

Once I started coding in earnest, implementing the helpers was simple enough. First came the parse method, to read a bunch of room events and extract a relevant and simplified corpus out of them. Of course, I wrote tests for and documented all code I wrote.

Before tackling the next helper method, I took a short detour and refactored a couple of methods to generalize and improve performance.

With that taken care of, I started working on the invert method, which was, thanks to Python, only about 5 lines long. Then came its tests, which took just slightly longer to complete.

Then I requested a review from my mentor @cvwright. With his review he helped me improve the parse method to prevent loss of significant "mega" tokens such as user mentions (@like:this.com) and room mentions (#this:is-a.room). The PR was merged shortly after that.

Next I quickly added a GitHub Actions workflow for CI to ensure the code is formatted properly and passing tests.

Once that was done, I worked on the calculate_parameters method, which simply determines the index and level parameters.

Searching, Normally

noreply@blogger.com (Aditya Rajput (BURG3R5)) — Mon, 06 Jun 2022 12:45:00 +0000

Before we can build a Symmetric Searchable Encryption scheme, we need to understand how searching works in a case where privacy isn't a concern.

Indexing

An index is, in our case, a mapping from a document id to that document's content. In the case of Matrix message events, the documents are non-redacted messages and their ids are the event ids.

So to create an index, we first obtain a list from the JSON file exported from a room.

Next, we iterate over the events and store the valid ones in a dict.

And we're done with indexing! If we wanted to, we could search by iterating over each document in messages and looking for the query in that message. The time complexity for such a searching operation would be O(<number of messages> × <average length of message>). That's terrible.

We can do much, much better. How? Well, by—

Inverting

A regular index consists of a mapping from document id to document content. An inverted index consists of a mapping from a token to a list of document ids in which it was found.

Tokens

A token is an atomic part of a document's content that can be searched for. For English and similar languages, this is a regular word that carries meaning. To obtain tokens from a documents string, we do the following:

Remove all punctuation from the string
Convert the string to lowercase
Split the string into a list of words
Remove any stopwords from the list

Once we've tokenized all the documents' contents, we extract all the unique keywords from them.

Armed with tokenized documents and a set of keywords, we can finally getting to inverting. The algorithm is simple: For each keyword, we find the list of documents containing that keyword and store their ids against the keyword itself.

Now what have we achieved? Well, the procedure to search over an inverted index is to a simple key lookup in the index. For a hash table, this takes O(1) time!

Conclusion

By doing a few extra operations while setting up our index, we've drastically reduced the time required for a search query to execute. But this system is not great for cases where privacy is valued. More on that in the next post about Leakages.

Further

If, instead of just storing the document ids, we store the document ids and the position where the keyword occurs, we can extend this system to phrase search. By looking for documents where two keywords occur in close proximity, we can let user search for phrases. However, I will not go into details because phrase search via proximity is even less privacy-friendly, and the SSE scheme that will be implemented in this project will not be using that.

Ciao for now!

Introduction

noreply@blogger.com (Aditya Rajput (BURG3R5)) — Fri, 03 Jun 2022 19:30:00 +0000

Hey there!

I'm Aditya Rajput, known in some circles as BURG3R5 and in others as @burgers:matrix.org.

(My favorite food is pizza; the nickname is ironic.)

This summer I'm gonna be implementing encrypted search in Matrix, a project under the Matrix.org organization for the Google Summer of Code program. I'll be mentored by Charles Wright (aka cvwright).

If you want to keep up with this project, you can join the public Matrix room #encrypted-search:matrix.org. You can also subscribe to this blog's RSS feed.

About Me

I'm a sophomore currently enrolled in a B.Tech. program at the Indian Institute of Technology at Roorkee, India. My love for computer science began when I was 14 years old and laid eyes on the Python docs on my family PC. I was fascinated by the idea of a perfect machine that worked according to a well-defined set of rules. From there, my love for programming grew exponentially as I learned about Java, C++, Flutter, Node.js, cryptography, reversing and so on.

Skills

Languages/Frameworks:

Dart: Flutter
Python: Django, Flask, numpy, pandas, scikit-learn
JavaScript/TypeScript: Node.js, Express.js, ReactJS
Java/Kotlin: Android Native

Tools: Linux-Bash scripting, Docker, Sentry, Heroku, Firebase, MongoDB, Vim.

About The Project

In this project I will implement, in particular, the keyword search scheme outlined in a Demertzis et al. paper titled “Fast Searchable Encryption with Tunable Locality”. I will achieve this by creating a Python library that exposes methods to create, update and search on encrypted indices stored in content repositories in a Matrix homeserver. As a part of the project, I will be demonstratively integrating the library into an existing Matrix client. Additionally, I will submit results of preliminary performance evaluation.

Goals

In this project I intend to:

Implement the keyword search SSE scheme outlined in the aforementioned Demertzis et al. paper.
Create encrypted indices of a few public Matrix rooms.
Implement an updation procedure for the above SSE i.e. provide a way to add new messages/documents to the encrypted index.
Integrate the project into a suitable client.
Perform performance evaluation of the created library.

Deliverables

A Python library that exposes methods to create, update and search on encrypted indices.
Demonstrative integration into a suitable Matrix client.
Complete documentation (comments and website) for the library and example codes.
Preliminary performance analysis results.
Weekly blogs on project progress.
GSoC end project report.

Pre-GSoC Code

In order to understand the paper and the project idea in the best way possible, I implemented a sort of MVP of this project before writing my proposal for this project. It helped me gain much insight into the project idea and also helped me set milestones. The code is available here. Included are tests, in which both keyword and phrase search are run over 500 messages exported from the official GSoC Matrix room (#gsoc:matrix.org).

About This Blog

On this blog I'll posting weekly updates about my progress with the project. I'll also be posting about interesting technical stuff I come across during my journey, whether it may be neat tricks or ugly bugs. I hope you'll accompany me on this journey.

See you next time!