A Pattern for Cross-Language Testing in Rust

This is the second part of a series of posts about rewriting Hypercore in Rust


There is little guidance on how to test Rust against code from other languages. After trying with several patterns, I found that the approach described here to be the most elegant.

I've been working on rewriting Hyperbee in Rust. Hyperbee is a BTree built on Hypercore, a peer-to-peer append-only log, originally written in JavaScript. I needed to be able to test my Rust code against the equivalent JavaScript. I'm also creating a Python Hyperbee library, that wraps the Rust, and so I need to test Python against the equivalent Rust. This is all part of the Rust Hypercore project which is working to rewrite all of Hypercore in Rust. Another goal rewrite, is to be able to use Rust's excellent Foreign Function Interface (FFI) to create libraries for other languages, starting with Python. So having a good pattern for cross language testing would prove useful throughout this project.

Key Benefits

No extra steps, just cargo test

Running your entire test suite through cargo test streamlines the testing process. As long as you have the foreign language runtime and make installed, there's no additional setup needed. This aligns with Rust developers' expectations - they're used to cargo test handling everything. No need to to remember to run a separate command likepytest or npm test. By avoiding these extra steps, we reduce friction and potential confusion in the development workflow.

Collocated Test Code

Writing foreign language test code directly within your Rust tests offers several advantages:

  • Test code lives alongside the Rust code it's testing
  • Clear documentation of test purpose through proximity
  • No need to manage hard coded values
  • Easy to extend tests as both implementations evolve
  • Reduced overhead from switching between files

This organization makes the tests more maintainable and self-documenting. When you need to understand how a piece of Rust code interacts with Python or JavaScript, everything you need is in one place.

How it works

Lets start with an example directory structure taken from Hyperbeee.

# crate root
tests/                  # Integration tests directory
  py_tests.rs           # Rust -> Python tests
  js_tests.rs           # Rust -> JavaScript tests
  common/
    Makefile            # Makefile for non-language specific stuff
    vars.mk             # Variables shared across Makefiles
    mod.rs              # Rust module
    ...
    python/             # Python specifics
      Makefile          # Run `make` to set up python dependencies
      mod.rs            # python specific rust code
      ...               # misc python files like requirements.txt
    javascript/         # JavaScript specifics
      Makefile          # Run `make` to set up js dependencies
      mod.rs            # javascript specific rust code
      ...               # misc js files: package.json, node_module, etc

Here *_tests.rs are Rust tests. Each Rust test file is compiled as a crate, from those crates common/ is seen as a Rust module. We will explain the innards of common later, but first we will start by looking at a test.

A Rust Test using Python

Let's dive into py_test.rs to see how this works

mod common;
use common::{
    python::{run_python},
    Result,
};
use hyperbee::Hyperbee;

#[tokio::test]
async fn hello_world() -> Result<()> {
    let storage_dir = tempfile::tempdir()?;
    {
        let hb = Hyperbee::from_storage_dir(&storage_dir).await?;
        hb.put(b"hello", Some(b"world")).await?;
        // drop `hb` so it does not lock `storage_dir`
    }
    let result = run_python(&format!(
        "
async def main():
    hb = await hyperbee_from_storage_dir('{}')
    res = await hb.get(b'hello')
    assert(res.value == b'world')
",
        storage_dir.path().display()
    ))?;

    assert_eq!(result.status.code(), Some(0));
    Ok(())
}

The actual test part is simple The Rust creates a Hyperbee and inserts the key b"hello" with value b"world", which is saved to storage_dir. Then Python opens a Hyperbee with the same storage_dir, and checks for the key value.

The way the test works is more interesting. At the top we declare mod common to make the common module available. We see this in the directory alongside py_test.rs. Within common we can have code exclusively for tests. We import common::python::{require_python, run_python}. These come from tests/common/python/mod.rs. Rust code in the commod module is general purpose test code. Code within the python and javascript modules is language specific Rust code.

Building test dependencies

To understand what's going on we step into run_python:

/// Run the provided python `code` within a context where the Python Hyperbee library is imported.
/// Code must be written within a `async main(): ...` function.
pub fn run_python(code: &str) -> Result<Output, Box<dyn std::error::Error>> {
    require_python()?;
    run_code(
        &build_whole_script(PRE_SCRIPT, code, POST_SCRIPT),
        "script.py",
        build_command,
        vec![path_to_python_target()?, path_to_c_lib()?],
    )
}

The first thing do is call require_python. This ensures that all the dependencies for running the python code are ready. It looks like:

pub fn require_python() -> Result<Output, Box<dyn std::error::Error>> {
    run_make_from_dir_with_arg(REL_PATH_TO_HERE, "")
}

It just calls run_make_from_dir_with_arg

pub fn run_make_from_dir_with_arg(dir: &str, arg: &str) -> Result<Output> {
    let path = join_paths!(git_root()?, dir);
    let cmd = format!("cd {path} && flock make.lock make {arg} && rm -f make.lock ");
    let out = check_cmd_output(Command::new("sh").arg("-c").arg(cmd).output()?)?;
    Ok(out)
}

This handles calling make from a certain location, with some arguments. Notice it makes use of flock. This creates a lockfile while make is running, or, if the file exists, it blocks until it is deleted. This lets us serialize all calls on the system to make. Which is important because the tests are run in parallel, and many of them may be trying to run make.

So require_python ultimately calls make within test/common/python/ which uses the Makefile in the python/ directory. We need to look at tests/common/python/Makefile to see what it does:

include ../vars.mk

# Build the Python Hyperbee library
$(TARGET_DEBUG_DIR)/hyperbee.py: $(C_LIB_PATH)
    cargo run -F ffi --bin uniffi-bindgen generate --library $(C_LIB_PATH) --language python --out-dir $(TARGET_DEBUG_DIR)

# Pull in the $(C_LIB_PATH) rule
include ../Makefile

First this gets some make variables defined in tests/common/vars.mk. We then use some of these in the Makefile "rule" called $(TARGET_DEBUG_DIR)/hyperbee.py. The rule should create the Python Hyperbee library at target/debug/hyperbee.py. The "recipe" part shows how this file is made, by running uniffi-bingen. Sidenote: we are using UniFFI for generating foreign language bindings. It's cool! I'll discuss this more in a future post.

Notice that the rule has $(C_LIB_PATH) (target/debug/libhyperbee.so) as a dependency. This rule is loaded in the include ../Makefile line, which is tests/common/Makefile. That Makefile handles cross language dependencies. We need to see haw it works:

# This file is loaded from other Makefile's so we can't use simple "include ../foo" because 
# that is resolved relative to the original Makefile.
#
# $(dir $(lastword $(MAKEFILE_LIST))) gets the dir of the current Makefile
include $(dir $(lastword $(MAKEFILE_LIST)))vars.mk

# Build Rust FFI library
$(C_LIB_PATH): $(RS_SOURCES) $(ROOT)/Cargo.toml
    cd $(ROOT) && cargo build -F ffi

This rule creates libhyperbee.so by running cargo. When libhyperbee.so8and hyperbee.py are ready, we have all the dependencies we need. Now that the dependencies are ready, lets look at how we run the Python code.

Running the foreign code

We saw in the run_python function, that it is a wrapper around the run_code function. The arguments run_code could use some explaining:

run_code(
    /// Create a string containing all the python code
    &build_whole_script(PRE_SCRIPT, code, POST_SCRIPT),
    /// The code goes in a file called "script.py"
    "script.py",
    /// A function creates a string, the string is the shell command that runs the code
    /// i.e. "python script.py"
    build_command,
    /// A vec of files copied next to "script.py"
    vec![path_to_python_target()?, path_to_c_lib()?],
)

Let's see what run_code does:

/// Put the provided `code` into a file named `script_file_name` inside a temporary directory where
/// `copy_dirs` are copied into. `build_command` should output a shell command as a string that
/// runs the script.
pub fn run_code(
    code: &str,
    script_file_name: &str,
    build_command: impl FnOnce(&str, &str) -> String,
    copy_dirs: Vec<PathBuf>,
) -> Result<Output> {
    let working_dir = tempfile::tempdir()?;
    let working_dir_path = working_dir.path().display().to_string();
    let script_path = working_dir.path().join(script_file_name);
    write!(&File::create(&script_path)?, "{code}")?;
    // copy copy_dirs into working dir
    for dir in copy_dirs {
        let dir_cp_cmd = Command::new("cp")
            .arg("-r")
            .arg(&dir)
            .arg(&working_dir_path)
            .output()?;
        if dir_cp_cmd.status.code() != Some(0) {
          // handle error
        }
    }
    let cmd = build_command(&working_dir_path, &script_path.to_string_lossy());
    Command::new("sh").arg("-c").arg(cmd).output()
}

Essentially this is just a way to run a shell command (from build_command()), in a temporary directory, with code inside of a file named script_file_name, with some context (copy_dirs).

Putting this all together, when we call:

run_python("
async main():
  run_python("print('hello world'))
")?;

We get a python script in a temporary directory (/tmp/.tmpDBK1j5/script.py) that looks like:

import asyncio
from hyperbee import *

async main():
  run_python("print('hello world'))

if __name__ == '__main__':
    asyncio.run(main())

hyperbee.py and libhyperbee.so are copied alongside script.py. Finally python scrip.py is run. The output of the process is returned by run_python as the Output type. This has the status code, stdout, and stderr. You can check values using print in python, then in Rust checking Output.stdout for the result.

Generalizing to other Languages

You may see how this would work for another language. In Hyperbee we apply the same pattern for JavaScript. The specifics are in tests/common/js/*. There I have a Makefile which handles setting up the JavaScript dependencies, so I can create a require_javascript function (like require_python). Then in js/mod.rs I implement run_javascript around the run_code function. For example there I would add a node_modules to the copy_dirs. With these I'm able to write tests the same way I did with Python.

Why Makefiles for Dependencies

make may seem confusing at first, but It's at it's core are some very simple principles. It is actually really powerful. Sure there are some hacks in here, but:

  • make is widely available and probably already installed on a developers machine.
  • It is language agnostic and provides a common interface for any language. Just run make.
  • It's declarative dependency model is self documenting.
  • It gives you incremental builds and caching. So we only rebuild what is needed.

I love make! But this is just a pattern. You could use something else for handling dependencies. But me, I love make!

Why use this module layout

The way module's work within tests/ was not well documented, or at least I could not find the documentation. So I arrived at this after trying several things. I knew that I wanted non-rust stuff like Makefiles, package.json, etc to live alongside their respective rust code. So this would imply I should have a directory for each language. You could imagine a more flat layout with js/, common/, and python/ all living under tests/. But this has the problem that then those modules could not see each other because tests/ is not actually a module. The individual files within it are compiled as crates. This has the effect that the layout of the modules tree depends on the test file itself, and so it could differ between test files. Recall that mod python has a dependency on mod common. So a test file that declares both mod python and mod common could work. But a test file could just declare mod python, which would not work because common is not in the modules.

Putting all non-test /utility modules under a tree fixes this by making a single, correct, entry point.

Downsides and pitfalls

For a small project a better approach might be just hard coding your expected values into the tests. This pattern requires correctly implementing a way to run foreign code, and automatically pull foreign dependencies. This isn't super hard, but it should be done with care. Ideally these things could be extracted into library.

To that end, I've been working on building a library for running foreign code in Rust with rusty_nodejs_repl. That library lets you write your states within a stateful Read-Eval-Print loop (REPL). This lets you mutate and check state from Node.js throughout the test like this:

let mut repl = Config::build()?.start()?;
let result = repl.run("
a = 42;
console.log(a)").await?;
assert_eq!(result, b"42\n");
// udate the state in the JavaScript
let result = repl.run("
a = a*2
console.log(a)").await?;
assert_eq!(result, b"84\n");

For examples of using this library see the Hypercore replicator library here.


If you have any questions or feedback, feel free to email me.. There is also a Discord Channel. If you'd like to contribute code, a good place to start is the Hypercore Rust project page. If you have more money than time, and want to support this work financially, consider contributing on my GitHub sponsors page.

Hypercore and Peer-to-Peer RSS

This is the first part of a series of posts about rewriting Hypercore in Rust


TL;DR This post describes my path through implementing a peer-to-peer RSS-like protocol with Hypercore in Node.js. Which motivated starting to work on a Rust Hypercore implementation. This also serves as a light introduction to Hypercore.


RSS and Hypercore

In late 2023 I had some extra time on my hands. I made a list of projects and interests that I might work on, and eventually settled on Hypercore, which I had heard it described as an append-only BitTorrent. I downloaded the whietpaper before a flight from L.A to Hong Kong. When I disembarked, I had decided I would try to use Hypercore to build a peer-to-peer RSS-like protocol.

RSS (or Atom), is a web-standard for creating and subscribing to a "feed" of updates. It is commonly used for distributing blogs and podcasts. Hypercore, being an append-only log, can provide something like a "feed" of data. Along with a way to share distribute updates in a peer-to-peer way. They seem like natural fit.

RSS's popularity has been waning in recent years as the way we get our "feeds" has been changing. Platforms (like Twitter, Youtube, Spotify, etc) prefer to keep users within their ecosystem, while pushing algorithmic feeds over chronological ones.

RSS's strength lies in aggregating content across platforms chronologically into one place. I believe there's room for a peer-to-peer alternative that preserves RSS's best qualities while adding modern distributed capabilities.

RSS's strength is that it allows you to aggregate your feeds across platforms into one place, and it chronological order, with a feed reader. Platforms don't like this, it makes users harder to track, advertise to, and lure into hours of scrolling. I think (or hope?) the pendulum will swing back to simple self-curated feeds when people get tired of being fed by an algorithm. I wanted a peer-to-peer RSS thing. Maybe other people do too. So I started working on it.

Implementation

I give a light introduction to Hypercore below and outline the implementation. If you just want to see the code, go here.

The Ecosystem

I don't recommend reading the white paper to get started, you should read the docs for that. To get started I needed to asses the ecosystem, look for prior work, libraries to use, etc. This was confusing so I'll summarize it here.

The project originally started as a thing called "Dat"; it was a way to share folders of large, mutable data in a peer-to-peer way. It came with a Node.js reference implementation. The original use-case was to solve the problem of link-rot for academic datasets. The peer-to-peer nature of Dat keeps data available because data is backed up by all peers; And because internally the data-structure is append-only, all history is preserved. So links are kept "alive" longer, and data behind a link cannot unexpectedly change.

At Dat's core it is the Hypercore append-only-log data-structure. A single Dat is composed several Hypercores combined to create a filesystem-like abstraction. Today this filesystem abstraction is contained in a library is called Hyperdrive. The project went through several iterations. Today the main Node.js implementation of Hypercore is being maintained and actively developed by Holepunch. Another important library to come out of Dat is a key-value store data structure called Hyperbee.

Here's a high-level dependency graph of Hypercore libraries.

dependencies

What is a Hypercore

It's helpful to understand more about Hypercore so we can understand of how to build something with it. Hypercore's API is like array with a append and get methods. In JavaScript this would be like Array with just the .push and .at methods. Or in rust a Vec with .append and .get.

Not just anyone can call append. When creating a Hypercore, it generates a key pair - the private key enables appending data, while the public key serves as a global identifier for peer discovery and allows peers to authenticate data. Peers connect through end-to-end encrypted channels. Since all data comes from the Hypercore authon, and all data is authenticated, this amounts to is only trusting the Hypercore author.

A key feature is sparse indexing - peers can efficiently download specific segments without requiring the entire dataset. So if there is a 100,000TB Hypercore dataset, you can efficiently download whatever small part of it you might want.

It was not obvious (to me) at first but you can do a lot with just append and get! Hyperbee is a key value store built on Hypercore with O(log n) lookups. I wrote a Rust implementation of Hyperbee. Read more about the algorithm here.

Building Hyper-RSS (HRSS) Peer

With those those basics we can dive into the implementation. For the core RSS feed-like data structure I wanted something like a "list" of "entries". Both the list and the entries should be able to carry some metadata (this could be: title, author, posted-at-time, etc). Each entry has a blob of data (this is the blog post, podcast, content, etc). It should be efficient and easy to get entries in reverse chronological order. I also need mutability for everything: metadata, entry-data, entry-ordering, etc.

For this I created OrderedHyperbee, which is a key-value store the preserves insertion order. It is a wrapper around Hyperbee that key-prefixes to create different "sub-databases" to keep a mapping between index, key, and value. This extra mapping between key and "index" lets us define an ordering. By default a newly inserted item is last. If a key is replaced it keeps it position" Metadata is stored in it's own key-prefixed sub-database. This has an API like:

class OrderedHyperbee {
  // get/set metadata
  async getMetadata(name)
  async putMetadata(name, value)
  // Insert a key & value in the last position
  async putOrderedItem(key, value)
  // Async generator over key value pairs from last to first
  async * getFeedStream()
}

There also needed to be a way to store binary blobs outside of an entry's data. Think of a podcast's RSS feed, it has an XML body which links to an audio file. You wouldn't want to include this binary audio data in the entry data itself. If you did, then loading a entry would potentially require loading a really big file. We essentially need separate key-value store for binary data. This is implmented in KeyedBlobs with the following API:

class KeyedBlobs {
  // Insert a blob with the given key
  async put(key, blob)
  // Get a whole blob
  getBlob (key)
  // Get a range of bytes within a blob with the given key
  getBlobRange(key, {start, end})
}

Up till now this has been agnostic to anything RSS specific. Now we combine these things into a Peer, which serves as the base for Reader and Writer. These are distinct because Writer needs to know how to write new items.

The current Writer implementation is totally based on converting an existing RSS feed into our format. This may seems limiting at first, but it allows using any tool you would regularly use to author RSS feeds, to create a Hyper-RSS (HRSS) feed. Writer contains the logic for taking an RSS entry downloading and extracting in media data, storing that in the KeyedBlobs, and rewriting links within the entry to point to KeyedBlobs; And saving the new entry in the OrderedHyperbee. Writer is also able to diff RSS feeds to find new entries and add them, see Writer.updateFeed().

Now we need to use it for something

A Hyper-RSS Client

I've implemented a simple HRSS feed reader for testing. It is intended to used as desktop app, with a web view UI. It's backend is in aggregator/ and the frontend is in web/. It's ugly but it works! See the README.md to try to use it.

I have some RSS feeds I've been using for testing. I am able to automatically pull updates from xkcd, and display them, with alt text!

I'm also able to stream audio from podcasts. This was surprisingly easy to implement on the backend. It just required handling HTTP Range headers, which was done using KeyedBlobs.getBlobRange mentioned above. Here it playing with Chapo Trap House.

Rewrite it in Rust

When I started building this, I quickly realized this would not really be useful except beyond a demo or experiment with Hypercore and RSS. Hypercore and it's Node.js libraries were great for making a demo. They're well built, it's suprisingly easy to build fairly complex and functional things with them.

However going demo, for HRSS to be actually useful, it has to broadly adopted, but relying on the Node.js libraries are an impediment toward that goal. It has to be a protocol that different things can speak across the internet. There needs to be an ecosystem of clients, authorship tools, libraries, HRSS indexes, etc. This is just an app.

Hypothetically, just as an example, suppose I went to the The Pirate Bay and asked them to support HRSS as a format for distributing TV series. Then (assuming they take me seriously at all) they would ask for a libraries and tooling to help them integrate the format. I can't give them this Node.js library because their backend is written PHP (I think).

Supposed they did implement HRSS, the next problem would be users need software to use HRSS. I could try to make everyone use my janky app, but a more successful adoption strategy would be integrating with existing RSS readers, podcast apps, or torrent clients. This brings us back to the problem of HRSS being written in Node.js, very few of the apps I'd want to integrate with written in Node.

This isn't just a problem with HRSS, it is a problem with the Hypercore ecosystem.

I'm not just hating on Node. For Hypercore to be successful it needs implementations across many platforms and languages. This led me to start working on the Hypercore Rust project. My goal is to complete use Rust's strong Foreign Function Interface(FFI) capabilities to generate bindings for multiple languages.

Rust Progress

I've made a lot of progress on the project in the past year. In that time I've: * Written Hyperbee from scratch. JavaScript version here. * Implemented the peer-to-peer replication protocol. JavaScript here. * Implemented Corestore. JavaScript here. * Implemented Hyperblobs. JavaScript here. * Pushed many changes upstream, some just fixes, others required for adding things like replication.

The last major part needed to before an entire Hypercore application can be built in rust is peer-discovery. The main JavaScript libraries required for this are Hyperswarm, Hyperdht, and dht-rpc. This work is on-going on GitHub here.


If you have any questions or feedback, feel free to email me.. There is also a Discord Channel. If you'd like to contribute code, a good place to start is the Hypercore Rust project page. If you have more money than time, and want to support this work financially, consider contributing on my GitHub sponsors page.


P.S. Suggestions for a better name than Hyper-RSS/HRSS are welcome!

Arbitrary code execution from pip's "—extra-index-url"

Once upon a time I made a python library, and gave it a very common name. Let's say the name was "foo". I also created a package that depended on foo, lets call it "bar". Both packages were in in my own private PyPI server, but something was wrong. When I installed bar the wrong dependency was being installed for foo. The package with the name foo from the public PyPI was being installed, not the one from my private PyPI.

I had inadvertently installed a package that could have run arbitrary code on my computer.

The problem occurs when --extra-index-url is used to point to a private PyPI that has packages with names shadowed on the public PyPI. When then this happens pip is needs to choose which PyPI to take the package from. It simply chooses the one with the higher version number.

This is a problem when: someone is using a private PyPI, with the --extra-index-url, and they are using a package on the private PyPI with a name they have not claimed on the public PyPI.

Going back to our original scenario, if an attacker controlled the name foo on the public PyPI, they could replace it with a malicious payload. The attacker could get control of the public foo name if it wasn't taken, or even if it was taken but unused (see PEP 541).

I think many people who have private python packages are vulnerable to having their packages hijacked like this.

I went looking around the internet. Here is one vulnerable PyPI instance I found.

CERN's vulnerable PyPI

CERN hosts many of it's own python packages here. Many of these packages names were not taken on the public PyPI, so I took them. Note that they also provide instructions to their users that they should use --extra-index-url.

I notified CERN that I had taken the names for their packages on the public PyPI and transferred ownership to them.

They offered to give me a tour if I was ever in Geneva :)

Upstream disclosure

I disclosed this to the security@python.org list. Unfortunately they said there is currently no path to fix this.

They recommended using "version-pinning and hash-pinning for deployments" to avoid this.

They also discussed shadowing the names of your own private packages on the public PyPI. This has problems because it reveals the names of packages you use, and forces you to effectively squat those names.

CVE-2018-20225

I reported this as a CVE. The link is here.

A Sketch of Trusted WiFi - Open, Authenticated, Encrypted

With the rise of Letsencrypt, the costs of TLS certificates has become essentially nothing. This opens up new possibilities for authenticated encryption for things other than https by leveraging the existing Internet Publick Key Infrastructure (PKI) and Domain Name System (DNS). Here I'll explain how we might use Letsencrypt to make WiFi safer.

When a WiFi network is setup for public use, there is trade off made between offering an unencrypted open access network vs an encrypted but password protected network. And neither of these options offers the ability for the client to authenticate that they have connected to the correct access point (AP).

We can leverage the Internet PKI to provide an open, authenticated, encrypted connection to the WiFi AP, just like we leverage PKI to get an open, authenticated, encrypted connection to https://wikipedia.com/

To clarify, we want 3 properties. Openness, meaning the client does not need to authenticate itself (e.g. it should not need to enter a password, or provide a client certificate). Authentication, meaning the AP's identity is verified. Encryption, meaning the connection between the client and AP is encrypted.

Protocol

The following protocol meets these requirements:

Alice, the WiFi provider, owns the domain name "alice.net". She creates a subdomain "wifi.alice.net" and obtains a signed TLS certificate from some certificate authority (CA) in the Internet PKI (Any CA can be used, not just Letsencrypt).

The AP then needs three things to be configured:

  • the AP should have the SSID "wifi.alice.net".
  • the AP should have the signed certificate for "wifi.alice.net", along with the corresponding private key.
  • the AP should use EAP-TLS with no client certificate (called EAP-UNAUTH-TLS?)

Alice turns on the WiFi.

Bob connects to the WiFi network named "wifi.alice.net", this establishes a connection with EAP-TLS. Additionally he checks that the X.509 certificate he received is for the domain "wifi.alice.net", and that it has a valid signature from a trusted CA.
QED

How'd that work?

We get openness by ensuring that the variant of the EAP-TLS protocol does not require a client certificate.

We get encryption with EAP-TLS.

The authentications is a little more subtle. We get authentication by checking that the certificate the AP serves us is the same as the SSID. This passes the work of "Authentication" to the CA who issues the certificate. Implicit here is that Bob, not his WiFi client, chooses "wifi.alice.net" because he knows that Alice owns that domain. Maybe he knows this because he is at Alice's house, or he's at Alice's internet cafe, or Alice.com is a know ISP for public WiFi etc.

Moving Forward

The pieces to implement this mostly exist. Only minor modifications are required to AP's and Clients. The only novel idea is comparing the SSID with the domain of the certificate to get authentication.

To get a proof of concept working, there are a few things to consider:

  • EAP-TLS with no client certificate is not well supported. There is interest and work in changing this. PoC's exist.
  • I don't know if you can simply "install" a certificate originally intended for TLS in place of a certificate intended for WiFi. They are both X.509 certificates.
  • Clients (wpa_supplicant) would need to be modified to compare the SSID with the domain in the certificate.

I'm working on it.

Adding Account Deactivation to Certbot

The recent ACME spec included a way for users to deactivate their accounts. This post describes adding this feature to certbot. This feature touches almost every level of certbot, so it gives an instructive look at Certbot's architecture.

An account in this case means the identity associated some key pair. Accounts control identifiers (domain names).

All the code describing the ACME protocol is in the acme/ package. The messages between the client and server are defined in certbot/acme/acme/messages.py So we can add the deactivation method here. From the ACME spec we see:

6.2.2.  Account deactivation

   A client may deactivate an account by posting a signed update to the
   server with a status field of "deactivated."  Clients may wish to do
   this when the account key is compromised.

   POST /acme/reg/asdf HTTP/1.1
   Host: example.com
   Content-Type: application/jose+json

   {
     "protected": base64url({
       "alg": "ES256",
       "jwk": {...},
       "nonce": "ntuJWWSic4WVNSqeUmshgg",
       "url": "https://example.com/acme/reg/asdf"
     })
     "payload": base64url({
       "status": "deactivated"
     }),
     "signature": "earzVLd3m5M4xJzR...bVTqn7R08AKOVf3Y"
   }

   The server MUST verify that the request is signed by the account key.
   If the server accepts the deactivation request, it should reply with
   a 200 (OK) status code and the current contents of the registration
   object.

   Once an account is deactivated, the server MUST NOT accept further
   requests authorized by that account's key.  It is up to server policy
   how long to retain data related to that account, whether to revoke
   certificates issued by that account, and whether to send email to
   that account's contacts.  ACME does not provide a way to reactivate a
   deactivated account.

Adding protocol messages in messages.py

So we crack open messages.py to add this message. In the module is the UpdateRegistration class which represents messages to the reg endpoint. And deactivating an account is actually just updating the "status" field to "deactivated". So deactivation is just a kind of updating. So all that is needed is to make UpdateRegistration accept a "status" field. We do this by adding an attribute to the class like:

status = jose.Field('status', omitempty=True)

Not so bad right?

Deactivation with the client in client.py

Now we need to use this thing we added. The acme package has a notion of a client, which is a thing that speaks the acme protocol. This is done in acme/client.py. Fortunately we already have code that sends update messages, so we use this to make a new function:

class Client(object):
    ...

    def deactivate(self, regr):
        """Deactivate registration."""
        update = {'status': 'deactivated'}
        body = messages.UpdateRegistration(**dict(update))
        ...
        # code for checking the response
        ...
        return new_regr

Testing the client

We have to mock out what we response from the CA. So we'd expect the current contents of the registration to be returned. It's pretty simple

    def test_deactivate_account(self):
        self.response.headers['Location'] = self.regr.uri
        self.response.json.return_value = self.regr.body.to_json()
        self.assertEqual(self.regr, self.client.deactivate(self.regr))

Adding a deactivate command to certbot

We are done in acme/. Now we move to certbot/ where all the non-protocol specific code lives. We have to add the pieces the user will interact with on the command line so cli.py is the place to start.

cli.py is where all the command line flags are parsed, including --update-registration. Which is similar to deactivation. So we add a thing:

    helpful.add(
        "register", "--deactivate", action="store_true",
        help="Irrevocably deactivate your account. Certificates associated "
             "with your account can still be revoked, but they can not be "
             "renewed.")

Now when certbot register --deactivate is entered, the python function certbot.main.main gets called which eventually calls certbot.main.register. The register function takes a config parameter. And because we used the --deactivate flag, this parameter has config.deactivate == True. So we can add the following code.

def register(config, unused_plugins):
    ...
    if config.deactivate:
        if len(accounts) == 0:
            add_msg("Could not find existing account to deactivate.")
        else:
            yesno = zope.component.getUtility(interfaces.IDisplay).yesno
            prompt = ("Are you SURE you would like to irrevocably deactivate "
                      "your account? You will lose access to the domains "
                      "associated with it.")
            wants_deactivate = yesno(prompt, yes_label='Deactivate',
                                     no_label='Abort', cli_flag='--deactivate',
                                     default=False)
            if wants_deactivate:
                acc, acme = _determine_account(config)
                acme_client = client.Client(config, acc, None, None, acme=acme)
                acme_client.acme.deactivate(acc.regr)
                add_msg("Account deactivated.")
            else:
                add_msg("Deactivation aborted.")
        return

This song and dance needed to get the deactivate method we made earlier isn't obvious. I basically copied part of this from other places in the code.

Next, this thing we added needs to be tested. So in certbot/tests/cli_test.py we add:

    @mock.patch('certbot.main._determine_account')
    @mock.patch('certbot.main.account')
    @mock.patch('certbot.main.client')
    @mock.patch('certbot.main.zope.component.getUtility')
    def test_registration_deactivate(self, mock_utility, mocked_client,
                                     mocked_account, mocked_det):
        mocked_storage = mock.MagicMock()
        mocked_account.AccountFileStorage.return_value = mocked_storage
        mocked_storage.find_all.return_value = ["an account"]
        mocked_det.return_value = (mock.MagicMock(), "foo")
        acme_client = mock.MagicMock()
        mocked_client.Client.return_value = acme_client

        x = self._call_no_clientmock(["register", "--deactivate"])
        self.assertTrue(x[0] is None)
        self.assertTrue(acme_client.acme.deactivate.called)
        m = "Account deactivated."
        self.assertTrue(m in mock_utility().add_message.call_args[0][0])

This isn't very pretty either. certbot/tests/cli_test.py is a big monolith, there is currently an issue for this.

Distarray Lightning Talk Slides

Last week I gave a lightning talk at the Austin Python User Group about the Distarray project which I've been working on at Enthought.

I briefly discussed what Distarray is, then compute the Julia set using both NumPy and Distarray. From my abstract:

Distarray is project which aims to allow NumPy arrays and operations to be easily distributed/parallelized, while maintaining a NumPy like interface. This is done by allowing the user to specify the array distribution across processes in array creation routines, these objects are the distarrays. We wrap IPython.parallel to do this.

We leverage PyTrillinos routines for parallel operations. PyTrillinos is being adapted to use the Distributed Array Protocol (another Enthought project). Here I present a demo for computing the Julia set, written 2 different ways. With pure NumPy, and with Distarray.

After the talk I had some interesting discussions about the architectural choices of distarray. In particular: Why did we choose IPython.parallel, and PyTrillinos?

IPython.parallel is problematic because its scaling is limited. Partially because it is built on zeromq (ØMQ), which lacks infiniBand support. Other backends of IPython.parallel have only been tested to scale to 10's of nodes.

From discussions with the team, there are two reasons we chose IPython.parallel.

  • It provides a unparalleled (no pun intended) level of interactivity.
  • Most jobs on supercomputers use less than 10 nodes (citation needed).

I can't speak much to the choice of PyTrillinos over something like PETSc. But PETSc does seem to have more users. In theory we could use PETSc if they decide to implement the distributed array protocol.

My slides:

Xubuntu Tweaks

My I recently upgraded my office computer to Ubuntu 13.04. Rebooting into the Unity environment was a total failure seemingly due to some graphics card/X11 issues. So I installed the xubuntu-desktop package instead of fooling around with graphics drivers/xorg.conf (relevant xkcd).

These are a few tweaks and hotkey changes that I made to match (standard?) Ubuntu hotkeys.

Ctrl + Alt + t to launch terminal

menu > Settings Manager > Keyboard > Application Shortcuts > Add

I chose to use the native xfce4-terminal so just enter that and bind it to your desired hotkey.

Application launcher takes 5 seconds to launch...

menu > Settings Manager > Keyboard > Application Shortcuts

At the bottom is xfrun4. Select it and change the command to xfrun4 --disable-server (source).

Ctrl + Alt + l lock workspace

menu > Settings Manager > Keyboard > Application Shortcuts

Change xflock4 to the desired hotkey.

Ctrl + Alt + Shift + Arrow to Move window to Arrow workspace

menu > Settings Manager > Window Manager > Keyboard

Find Move window to * workspace then bind as desired.

Wrapping Up Google Summer of Code

My Summer has been over for a while, but GSoC is officially ending this week. And what do I have to show?

  • SciPy's sparse matrices now support boolean data.
  • Sparse matrices now support boolean operations (!=, <=, etc.).
  • NumPy universal functions (ufuncs) can now be overridden for compatibility.
  • Sparse matrices uses this ufunc override functionality to do sensible things when acted on by ufuncs.
  • Support fancy indexing.
  • Axis arguments for min and max methods.
  • various other things: speed ups, small features, test coverage, bugs fixes, code clean ups, and a few backports.

But I think that I have benefited personally from this experience much more than SciPy has. I learned so much this summer, a short list of things I know vastly more about than I did before this summer:

  • PYTHON. Jeez looking at code I wrote before this summer is painful.
  • The Python and NumPy C API, before this summer I was a total C noob. Now I can scratch together a python API in C.
  • SciPy.
  • NumPy, numpy.frompyfunc is awesome.
  • Git, before this summer I could commit thing to my own repos and that was pretty much it. Git hooks are awesome.
  • In general, development workflow.

I grown attached to SciPy and am excited I can make meaningful contributions to that are actually helping people. But contributing more will have to wait untill after the GRE, grad school applications, and my senior thesis. There are a few things I would like to add down the road to incorporate into SciPy 1.0. e.g. 64bit indices, change spares matrices to emulate numpy.array rather than numpy.matrix. I would also like to see if I can apply ufunc overrides in a few other places that mix numpy.array and scipy.sparse like scikit-learn.

Here is a link to git log -p upstream/master --author="Blake Griffith" in numpy and scipy.

Fancy Indexing in Sparse Matrices

Recently I've been working on a pull request for fancy indexing in sparse matrices. Most of the work has already been done by Daniel Smith (thanks!). I've been working on fixing some bugs that were causing test failures. And cleaning up the interface.

Below is some data I will be working with throughout this post.

In [1]:
import numpy as np
import scipy.sparse as sp

A = np.asmatrix(np.arange(50).reshape(5, 10))
Asp = sp.csr_matrix(A)

Empty Indexing

Python is pretty forgiving in what it allows for indexing with slices. For example it does not raise an error when the upper bound of a slice is outside of the object. Things like list(range(3))[:9000] are perfectly legal. Here I adopted python's forgiveness when implementing how sparse matrices should be have when indexing should return something empty.

What should happen when indexing should return an empty matrix? With ndarrays, a matrix of "size" 0 is returned. Where is size is all the elements of shape multiplied:

In [2]:
A[1:1], A[1:2:-1]
Out[2]:
(matrix([], shape=(0, 10), dtype=int64),
 matrix([], shape=(0, 10), dtype=int64))

However in scipy.sparse there is currently no way to create a size 0 matrix. There is an explicit requirement in the sparse matrix base class that both entries of shape be >= 1. So the next best thing I could do is to return a size 1 matrix with a (1,1) shape and a single zero element. This is currently supported by all sparse matrix formats. The result of fancy indexing is sometimes created using the coordinate sparse matrix format (COO). A small change in its __init__ method now has it return a (1, 1) empty COO matrix when you try to create a COO matrix which would haze size 0. There was also a change to how slices are checked to allow the start and stop arguments to be equal, and if so to return an empty matrix as described above. So now we have:

In [3]:
Asp[1:1], Asp[1:2:-1]
Out[3]:
(<1x1 sparse matrix of type '<class 'numpy.int64'>'
	with 0 stored elements in Compressed Sparse Row format>,
 <1x1 sparse matrix of type '<class 'numpy.float64'>'
	with 0 stored elements in Compressed Sparse Row format>)

Sparse Boolean Indexing

I also add a new feature to the fancy indexing. Since Boolean sparse matrices work now, I added support for indexing with them. So this works:

In [4]:
Asp[Asp > 30] = 42
Asp.todense()
Out[4]:
matrix([[ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9],
        [10, 11, 12, 13, 14, 15, 16, 17, 18, 19],
        [20, 21, 22, 23, 24, 25, 26, 27, 28, 29],
        [30, 42, 42, 42, 42, 42, 42, 42, 42, 42],
        [42, 42, 42, 42, 42, 42, 42, 42, 42, 42]], dtype=int64)

Supporting this was mostly a matter of allowing existing code paths to accept the sparse matrices.

However the boolean indexing is not completely analogous to NumPy. Since sparse matrices cannot be one dimensional. So there is no way to do something like.

In [5]:
bool_vector = np.random.randint(2, size=5).astype(np.bool)
A[bool_vector]
Out[5]:
matrix([[ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9],
        [20, 21, 22, 23, 24, 25, 26, 27, 28, 29]])

CSC's .nonzero method

There was still a bit of work to do with CSC. The CSC __getitem__ was simplified to just two cases. The first is the case where a sparse matrix is returned, the second is the case where a sequence of elements is returned. However there was still a bug which was causing problems. The csc_matrix.nonzero method was return its indices sorted incorrectly. NumPy states that ndarray.nonzero should sort it's indices C-style, with the last entry varying the fastest. However the indices in this case were sorted with the first index varying the fastest.

I fixed this by defining a .nonzero method in the csc_matrix class to override the method defined in the base class (spmatrix). I tried to fix this in a few other ways. Like by resorting the indices in _cs_matrix.tocoo which is used to define the base .nonzero but this caused a lot of round off problems for some reason I could not figure out.

Week-9 Ufunc Overrides

This week I'm still working on the pull request for ufunc overrides, however I think it is finally nearing completion. The implementation is working as described and all tests are passing. I'm looking forward to working on SciPy again.

The main aspects I've been working on are ufunc overrides method resolution order, and argument normalization.

Method Resolution Order (MRO)

Python functions in certain cases have a special MRO which is a bit more complicated than the default left to right. Whenever ther right argument is a subtype of the left argument its special method corresponding to the calling function is called first. So for example, add(a, b) would normally call a.__add__(b) but if b is a subtype of a, then b.__radd__(a) is called. However there are no examples in the Python standard library of a ternary or greater function from which we can copy. So we have tried to generalize this concept to a higher order.

The MRO algorithm is succinctly stated by @njsmith as:

While there remain untried inputs, pick the leftmost one which does not have a proper subtype still remaining to be checked.

Where inputs are the inputs to the ufunc. Trying an input refers to calling its __numpy_ufunc__ method (if it has one) and seeing that it does not return NotImplemented.

So Basically if a ufunc has three inputs (a, b, as) in that order, where as is a subtype of a. They will be tried in the order b > as > a.

Argument Normalization

Many of NumPy's ufuncs can take a out argument, which specifies where the output of the ufunc is assigned. The out argument can be passed as either a positional, or keyword argument. So naïvely checking a ufuncs arguments for __numpy_ufunc__ and then passing said arguments unaltered is not always sensible. So given nargs - the number of args, and nin - the number of inputs, we can check for an out positional argument and move it to the keyword arguments. The normalized arguments are then passed the __numpy_ufunc__ method.