Setting up SPIRE for your Kubernetes cluster

About SPIFFE and SPIRE

If you're reading this, you likely already know what SPIFFE and SPIRE are. But in case you don't here is a really short summary: SPIFFE (Secure Production Identity Framework for Everyone) is a specification and SPIRE (SPIFFE Runtime Environment) an implementation of that specification for securely issuing identities to workloads running in different compute environments, and for managing these identities (such as refreshing, revoking, etc.). Why is it useful? Well, it lets your services, such as pods running in Kubernetes, to have their own certificates and signed JWTs, which are automatically refreshed, etc. and using which they can authenticate themselves to other services, and communicate securely with them. For example, the certificates could be used to create mTLS connections with other workloads, or signed tokens could be used as a proof-of-possession for authentication.

One key problem of securely issuing identities is the security of the initial handshake, for the initial request asking for identity. SPIRE solves this in a novel way using agents that are capable of querying the compute environment about the workloads requesting identities, and then issuing the identities only if these workloads satisfy certain criteria. By keeping the agents local to the node where the workloads run, concerns about the initial secrets are addressed. Of course there is a lot more to it, and the right place to head to for more details is here.

Motivation

I had trouble wrapping my head around exactly what was going on and I still have many questions about it, but I figured that the best way to learn about this was to try it out. The purpose of this post was to document the steps for doing so, focusing on deploying SPIRE for workloads on a Kubernetes cluster. It's not particularly hard to do this by following the official documentation, but this is a more linear version of it, focusing on a specific and commonly useful scenario. So I hope to make it a wee bit easier with this post.

Architecture

We will build a setup that can serve one or more Kubernetes clusters. In order to support this, we would use a relatively recent Kubernetes version (1.22+) that supports projected service account tokens (PSATs).

We will deploy a single SPIRE server running outside the k8s cluster(s). In each cluster (we will use only one), we will deploy a SPIRE agent daemonset. Each SPIRE agent instance would connect to the SPIRE server (either securely or insecurely) at bootstrap and receive the node identity. The SPIRE server and each SPIRE agent instance would securely connect to the kube API of each k8s cluster to query k8s metadata about nodes and workloads.

Deploying the SPIRE Server

Deploy the server on a Linux box which can access your k8s cluster API. For example, I am using my Ubuntu laptop which acts as the host for my k8s VMs.

Create the spire user and spire group. 

$ sudo groupadd spire
$ sudo useradd -g spire -s /bin/false -M -r spire

Download the binary bundle and copy it to /opt/spire.

$ wget https://github.com/spiffe/spire/releases/download/v1.6.1/spire-1.6.1-linux-x86_64-glibc.tar.gz
$ tar xfz spire-1.6.1-linux-x86_64-glibc.tar.gz
$ sudo cp -r spire-1.6.1/ /opt/spire/
$ sudo find /opt/spire -type d -exec chmod 755 {} \;
$ sudo chmod 755 /opt/spire/bin/spire-server
$ sudo chown spire:spire /opt/spire/conf/server/server.conf
$ sudo ln -s /opt/spire/bin/spire-server /usr/bin/spire-server

Edit the server configuration present at /opt/spire/conf/server/server.conf thus.

server {
    bind_address = "192.168.219.1"
    bind_port = "8081"
    trust_domain = "everett.host"
    data_dir = "/var/opt/spire/data/server"
    log_level = "DEBUG"
    log_file = "/var/opt/spire/log/server.log"
    ca_ttl = "168h"
    default_x509_svid_ttl = "28h"
}

Set the bind_address to an address that is accessible from the k8s nodes. In my case, it is the VirtualBox host network IP of the Ubuntu host, which happens to be the gateway IP for that network. Keep the bind_port as 8081 or a different port above 1023 if you know 8081 conflicts with another application.

Set the trust_domain to a unique string - it need not be DNS resolvable. In my case, the hostname of the Ubuntu laptop where the SPIRE server is running is everett, so I set trust_domain to everett.host. Also ensure that ca_ttl is at least six times the value in default_x509_svid_ttl.

The data_dir directory specifies a directory under which most application data would be persisted. Likewise, the log_file directive specifies the log file name. I made sure I ran the following commands to make these directories accessible.

$ sudo mkdir -p /var/opt/spire/data
$ sudo mkdir -p /var/opt/spire/log
$ sudo chown -R spire:spire /var/opt/spire/

In the plugins section of the same file, update the DataStore, KeyManager, UpstreamAuthority, and NodeAttestor plugins.

For the SQL data store,  keep the database_type as the default sqlite3, and update the connection string to point to the location under data_dir where the data files would be stored, as shown below.

plugins {
    DataStore "sql" {
        plugin_data {
            database_type = "sqlite3"
            connection_string = "/var/opt/spire/data/server/datastore.sqlite3"
        }
    }

For the key manager disk plugin, specify the location where the server private keys would be kept as shown. Here we use an unencrypted directory store for our purposes, but for better security one should use more secure secret stores or key management systems.

     KeyManager "disk" {

        plugin_data {
            keys_path = "/var/opt/spire/data/server/keys.json"
        }
    }

Add the UpstreamAuthority stanza if it's not present, or configure it as shown below. It configures the X509 certificate and private key used by the server to issue certificates. You need to know what you're doing, but you can read the nifty script at this site, then tweak it as needed and use that to generate a root cert and key pair, and a leaf cert and key from it. Rename the root cert and key to bootstrap.crt and bootstrap.key, copy them over to /var/opt/spire/data/server, and remember to update their permissions so that they are accessible by the spire user and spire group.

    UpstreamAuthority "disk" {
        plugin_data {
            key_file_path = "/var/opt/spire/data/server/bootstrap.key"
            cert_file_path = "/var/opt/spire/data/server/bootstrap.crt"
        }
    }

Finally, for each k8s cluster that this SPIRE server needs to serve, ensure a section is available as shown in bold below. The kube_config_file points to the location of the k8s config used to access the cluster's kube-api. Ensure that this file is copied from the k8s cluster to the location listed here. The cluster identifier in this case is e1, which is arbitrarily chosen - you can give it any name but make sure to use the same name to refer to it elsewhere too. The service_account_allow_list lists the service accounts from the e1 cluster that are allowed to connect to the SPIRE server. The SPIRE server would validate the service account token by using the k8s Token Review API on the cluster e1.

    NodeAttestor "k8s_psat" {
        plugin_data {
            clusters = {
                "e1" = {
                    service_account_allow_list = ["spire:spire-agent"]
                    kube_config_file = "/home/amukher1/.kube/config"
                }
            }
        }
    }
Ensure that the spire user has read access to the path listed for kube_config_file.

Next, create a systemd module for automatically starting and stopping the SPIRE server on this node. Create the file /etc/systemd/system/spire-server.service and set its content to the following.

[Unit]
Description=SPIRE Server

[Service]
User=spire
Group=spire
ExecStart=/usr/bin/spire-server run -config /opt/spire/conf/server/server.conf

[Install]
WantedBy=multi-user.target

Then enable and start the service, and check its status using:

$ sudo systemctl daemon-reload
$ sudo systemctl enable --now spire-server
$ sudo systemctl status spire-server

In case you are running this on a host that runs guest VMs in VirtualBox, and the SPIRE server listens on an IP of the host-only network that the VMs too are a part of, then that network would not be up till you bring up your first VM. Till such time, the SPIRE server could fail to start as it is unable to bind to an address off of that network. This is the reason I have not configured the service to restart automatically. Instead, you can just manually start it using the following command, once you've started the first VM:

$ systemctl start spire-server

Deploying the SPIRE Agent

The agent must be deployed as a daemonset on each k8s cluster that you want to manage via this server. We would need certain manifest yamls for deploying the agent. We could get this from the source bundle, downloaded from the page here.

$ wget https://github.com/spiffe/spire/archive/v1.6.1.tar.gz
$ tar -xf v1.6.1.tar.gz spire-1.6.1/test/integration/suites/k8s/conf/agent/spire-agent.yaml --strip-components=7

Then edit the file spire-agent.yaml as below.

In the spire-agent ConfigMap manifest inside this file, edit the contents of agent.conf, setting the following keys:

server_address = "<SPIRE_server_addr>"

This should be the IP or the FQDN where the SPIRE server is accessible - typically the same as the bind_address in the server config, or an FQDN resolving to it.

Also set the trust_domain to the same value as set for the server:

trust_domain = "everett.host"

Make a note of the trust_bundle_path attribute. This is the location within the SPIRE agent pod where the CA cert bundle of the SPIRE server should be mounted. It is okay to keep it set to its default value of /run/spire/bundle/bundle.crt. On first run you may want to comment out this attribute and instead add the following.

insecure_bootstrap = true

Within the NodeAttestor stanza, set the cluster attribute to e1.

      NodeAttestor "k8s_psat" {
        plugin_data {
          cluster = "e1"
        }
      }

In the WorkloadAttestor stanza, set the directive skip_kubelet_verification to false, and set the kubelet_ca_path attribute to the location CA cert for this k8s cluster as shown below.

      WorkloadAttestor "k8s" {
        plugin_data {
          ...
          # skip_kubelet_verification = false
          kubelet_ca_path = "/run/spire/bundle/kubelet-ca.crt"
        }

We will ensure that the k8s cluster CA cert is mounted at the location pointed at by kubelet_ca_path, via a ConfigMap.

Further down in the manifest, edit the containers section of the DaemonSet spec, updating the SPIRE agent image location, and image pull policy.

     containers:
        - name: spire-agent
          image: ghcr.io/spiffe/spire-agent:1.6.1
          imagePullPolicy: IfNotPresent 

Copy the CA cert of your k8s cluster from /etc/kubernetes/pki/ca.crt to the local directory, naming the target file kubelet-ca.crt.

If you did not set insecure_bootstrap to true earlier, then retrieve the CA cert bundle for the SPIRE server that was set aside, and copy it to some location from where you can create ConfigMaps on this cluster. Rename the file to bundle.crt. 

Then run the following command, include the bundle.crt only if you copied it.

$ kubectl create configmap spire-bundle -n spire --from-file=kubelet-ca.crt --from-file=bundle.crt

Finally, apply this edited manifest on your k8s cluster. 

$ kubectl apply -f spire-agent.yaml

If all goes well, you should have a working SPIRE installation on your k8s cluster. You can verify that the SPIRE agent daemonset has pods running on each worker node of your cluster by running the following command.

$ kubectl get pods -n spire

Make sure that the pods are running and ready. Also run the following commands on the SPIRE server to verify that the SPIRE agents on your nodes have been attested and received SPIFFE ids. You can get agent SPIFFE ids from the output of the first command.

$ spire-server agent list
$ spire-server agent show -spiffeID <spiffe_ID>

Cleaning up

While experimenting with the setup, one would likely need to clean up and recreate the setup several times. When doing that, it's good to follow a certain discipline. With all nodes of the cluster up, run the following commands.

$ kubectl delete -f spire-agent.yaml -n spire
$ kubectl delete configmap spire-bundle -n spire
$ kubectl delete ns spire
$ kubectl get all,configmap,sa -n spire

Other than the default service account and a ConfigMap called kube-root-ca.crt, all other resources should be deleted. Still check for any stray pods:

$ kubectl get pods -n spire

Using SPIRE

In this section, we shall see how to use SPIRE to have identities issued to workloads running within your Kubernetes cluster. 

Architecture

We would deploy a pod on Kubernetes to fetch its identity bundle from the SPIRE agent running locally on that node. It would connect to the agent over a Unix domain socket mounted from a host path. We must also create registration entries for the workloads. Typically we would want to do this by defining criteria for choosing a workload, using selectors. We want to create the rules such that given a pod running a particular image X and with a particular label app=Y, we would always issue it the same identity no matter which worker node it runs on. To do this, the parent spiffe ID of the registration entry cannot be that of a single worker node, but of an alias to all the worker nodes. The following section describes these in detail.

Process

Run the command below on the server to create a node alias SPIFFE id that applies to all worker nodes of the cluster. This will allow us to create registration entries for workloads that would give them the same identity based on their image and a label, irrespective of which cluster node they run on.

/opt/spire/bin/spire-server entry create -node -spiffeID spiffe://everett.host/ns/spire/sa/spire-agent/cluster/e1 -selector k8s_psat:cluster:e1 -selector k8s_psat:agent_ns:spire -selector k8s_psat:agent_sa:spire-agent

Next, create a binary using the following Go code. This binary fetches its identity and bundles from the SPIRE agent running locally on a worker.

package main

import (
    "context"
    "fmt"
    "log"
    "net/http"
    "os"
    "strings"
    "time"

    "github.com/spiffe/go-spiffe/v2/spiffeid"
    "github.com/spiffe/go-spiffe/v2/svid/jwtsvid"
    "github.com/spiffe/go-spiffe/v2/workloadapi"
)

const (
    socketPath = "unix:///tmp/spire-agent/api.sock"
)

func main() {
   ctx := context.Background()
    for err := run(ctx); ; {
        if err != nil {
            log.Fatal(err)
        }
        time.Sleep(60 * time.Second)
    }
}

func run(ctx context.Context) error {
    // Set a timeout to prevent the request from hanging if this workload is not properly registered in SPIRE.
    ctx, cancel := context.WithTimeout(ctx, 30*time.Second)
    defer cancel()

    client := workloadapi.WithClientOptions(workloadapi.WithAddr(socketPath))

    // Create an X509Source struct to fetch the trust bundle as needed to verify the X509-SVID presented by the server.
    x509Source, err := workloadapi.NewX509Source(ctx, client)
    if err != nil {
        fmt.Printf("unable to create X509Source: %v", err)
        return fmt.Errorf("unable to create X509Source: %w", err)
    }
    defer x509Source.Close()

    fmt.Printf("Received trust budle: %v", x509Source)
    serverID := spiffeid.RequireFromString("spiffe://example.org/server")

    // By default, this example uses the server's SPIFFE ID as the audience.
    // It doesn't have to be a SPIFFE ID as long as it follows the JWT-SVID guidelines (https://github.com/spiffe/spiffe/blob/main/standards/JWT-SVID.md#32-audience)
    audience := serverID.String()
    args := os.Args
    if len(args) >= 2 {
        audience = args[1]
    }

    // Create a JWTSource to fetch JWT-SVIDs
    jwtSource, err := workloadapi.NewJWTSource(ctx, client)
    if err != nil {
        fmt.Printf("unable to create JWTSource: %v\n", err)
        return fmt.Errorf("unable to create JWTSource: %w", err)
    }
    defer jwtSource.Close()

    // Fetch a JWT-SVID and set the `Authorization` header.
    // Alternatively, it is possible to fetch the JWT-SVID using `workloadapi.FetchJWTSVID`.
    svid, err := jwtSource.FetchJWTSVID(ctx, jwtsvid.Params{
        Audience: audience,
    })
    if err != nil {
        fmt.Printf("unable to fetch SVID: %v\n", err)
        return fmt.Errorf("unable to fetch SVID: %w", err)
    }
    fmt.Printf("Received JWT svid: %v", svid)
    return nil
}

I named this binary id-client, and created a docker image tagged amukher1/id-client and pushed it to DockerHub. You can use a name of your choice. Deploy this binary with the following manifest:

apiVersion: v1
kind: Pod
metadata:
  name: id-client
  labels:
    app: id-client
spec:
  containers:
  - name: id-client
    image: amukher1/id-client
    volumeMounts:
    - name: spire-agent-socket
      mountPath: /tmp/spire-agent
      readOnly: false
  volumes:
  - name: spire-agent-socket
    hostPath:
      path: /run/spire/agent-sockets
      type: DirectoryOrCreate

Make a note of the image tag of the container image. I used the following command and copied the first value inside the RepoDigests array:

docker inspect amukher1/id-client

Now create a registration entry for a workload matching this binary, using the node alias as the parent SPIFFE id.

/opt/spire/bin/spire-server entry create -spiffeID spiffe://everett.host/image/id-client -parentID spiffe://everett.host/ns/spire/sa/spire-agent/cluster/e1 -selector k8s:pod-image:docker.io/<image tag> -selector k8s:pod-label:app:id-client

With the above steps, you should be able to fetch x509 certificates as well JWT tokens.

Read more!

Routing TCP over Envoy using HTTP CONNECT

Tunneling TCP traffic using the L4 proxy capabilities of Envoy works well, but due to the nature of TCP, very little metadata useful for routing can be propagated via the TCP protocol itself. Using the HTTP CONNECT verb however, it is possible to instruct a proxy to tunnel the subsequent data as raw TCP to some target without interpreting it as http or some other L7 protocol. The way it works is listed below:

1. A caller A wants to send some TCP traffic to a service B.
2. The caller A calls some proxy P by making an HTTP request with the following header: CONNECT http://<address_of_B>[:port] HTTP/1.1
3. The proxy P opens a TCP connection to the address and the optional port, and keeps the connection from A open.
4. The caller A then uses its connection to P to stream the TCP payload it needs to send to B. P relays this traffic to B.

In the above, P is said to terminate the HTTP CONNECT. Equally well, it could be configured to propagate the HTTP CONNECT instead of terminating it, proxying everything it receives to a downstream proxy (upstream, if we use Envoy terminology). The final proxy in this chain would then terminate the HTTP CONNECT and forward the request to the target.

The elegance in this approach is that by encapsulating the request in an HTTP shim, we open up HTTP headers as a mechanism for specifying routing directives that the intermediate proxies could use. If the caller uses TLS, they can specify the serverName in TLS headers and use SNI for routing the request. The actual target address of B need not even be routable from A - it only needs to be routable from the final proxy in the chain (the one that terminates the HTTP CONNECT). With HTTP/2, the CONNECT header even allows a URL path. I'm not sure but perhaps this URL path too could be used for routing purposes just as with regular requests. With HTTP/2, multiple TCP streams could be multiplexed over a single HTTP/2 connection, achieving improved resource usage and better latencies when reusing connections from a pool.

The obvious downside is that the caller A would need to know the mechanics of HTTP CONNECT and have a dependency on it. But this is a small price to pay for not having to deal with TCP routing.

Envoy has supported HTTP CONNECT for a few years now (possibly since 1.14.x). Here is a small sample configuration which uses two Envoys, one propagating the HTTP CONNECT and the other terminating it, to route TCP traffic to a destination.

static_resources:
  listeners:
  - name: listener_0
    address:
      socket_address: { address: 127.0.0.1, port_value: 10000 }
    filter_chains:
    - filters:
      - name: envoy.filters.network.http_connection_manager
        typed_config:
          "@type": type.googleapis.com/envoy.extensions.filters.network.http_connection_manager.v3.HttpConnectionManager
          stat_prefix: ingress_http
          codec_type: AUTO
          route_config:
            name: local_route
            virtual_hosts:
            - name: connect_tcp
              domains: ["fubar.xyz:1234"]
              routes:
              - match: { headers: [{name: ":authority", suffix_match: ":1234"}], connect_matcher: {} }
                route: { cluster: ssh, upgrade_configs: [{upgrade_type: "CONNECT", connect_config: {}}] }
              - match: { prefix: "/" }
                route: { cluster: ssh }
            - name: local_service
              domains: ["*"]
              routes:
              - match: { prefix: "/" }
                route: { cluster: ssh }
          http_filters:
          - name: envoy.filters.http.router
            typed_config:
              "@type": type.googleapis.com/envoy.extensions.filters.http.router.v3.Router
          upgrade_configs:
          - upgrade_type: CONNECT
          http2_protocol_options:
            allow_connect: true
  - name: listener_1
    address:
      socket_address: { address: 127.0.0.1, port_value: 9000 }
    filter_chains:
    - filters:
      - name: envoy.filters.network.http_connection_manager
        typed_config:
          "@type": type.googleapis.com/envoy.extensions.filters.network.http_connection_manager.v3.HttpConnectionManager
          stat_prefix: ingress_http
          codec_type: AUTO
          route_config:
            name: local_route1
            virtual_hosts:
            - name: connect_fwd
              domains: ["fubar.xyz", "fubar.xyz:*"]
              routes:
              - match: { connect_matcher: {} }
                #### route: { cluster: conti, upgrade_configs: [{upgrade_type: "websocket"}]}
                route: { cluster: conti, timeout: "0s"}
              - match: { prefix: "/" }
                route: { cluster: conti1 }
            - name: local_service
              domains: ["*"]
              routes:
              - match: { prefix: "/" }
                route: { cluster: conti1 }
          http_filters:
          - name: envoy.filters.http.router
            typed_config:
              "@type": type.googleapis.com/envoy.extensions.filters.http.router.v3.Router
          upgrade_configs:
          - upgrade_type: CONNECT
          http2_protocol_options:
            allow_connect: true
  clusters:
  - name: ssh
    connect_timeout: 0.25s
    type: STATIC
    lb_policy: ROUND_ROBIN
    load_assignment:
      cluster_name: ssh
      endpoints:
      - lb_endpoints:
        - endpoint:
            address:
              socket_address:
                address: 127.0.0.1
                port_value: 22
  - name: conti
    connect_timeout: 0.25s
    type: STATIC
    lb_policy: ROUND_ROBIN
    load_assignment:
      cluster_name: conti
      endpoints:
      - lb_endpoints:
        - endpoint:
            address:
              socket_address:
                address: 127.0.0.1
                port_value: 10000
  - name: conti1
    connect_timeout: 0.25s
    type: STATIC
    lb_policy: ROUND_ROBIN
    load_assignment:
      cluster_name: conti
      endpoints:
      - lb_endpoints:
        - endpoint:
            address:
              socket_address:
                address: 127.0.0.1
                port_value: 8000

(More explanation to follow.)

Read more!

Charting Your Course Through the Knowledge Economy

This is the age of the knowledge economy and the age of the autodidact. Formal education matters less than skills and the ability to think deeply, and to apply one's understanding of an area. Very little of the learning we need to do from here on would be formulaic. Multiple levels of formulaic thinking, with sophisticated patterns, would be delegated to machines and human intellectual power would be repeatedly summoned to solve hard problems. But that journey of a thousand miles would still need to start with a single step. This article is about building the intellectual discipline to absorb and produce knowledge, and hopefully, some wisdom too.

Learning discipline for the attention challenged

How do you study deep when you have attention span issues (like most of the early 21st century workforce) and need to understand and remember quickly? I don't have an answer, I am seeking answers myself. Two things I can think of though, are:

1. Drawing diagrams with labels, *on paper*, illustrating the main ideas, if that's feasible.
2. Avoiding phone, social media, and similar modern day "necessities" at all costs at study time.

There is a third thing, and this was popularized by the course / book on learning how to learn, but is possibly well-known:

1. Recap what you read later (maybe the next morning or the same day in the night) using the drawing, and perhaps write notes. And then of course read this in about a week.

Building a reading list

If you're like me, you'd buy books, but read only a small subset of them. It's not inherently problematic and there is some evidence to say that having books you haven't yet gotten to reading might be a good thing - but it can only be so as long as you read with some regularity and burn down a reading list. Which means sporadic reading is not such a great idea.

An even harder problem presents itself with e-books. We download a great e-book that we always wanted to read and then forget about it. The greatest challenge with e-books is that they are not in front of your eyes, on your bookshelf or table, constantly reminding you of their existence. How does one remember them, and then make a mental note of a plan to read them? Again I don't know the answer, but here is something I can think of.

1. Have a reading list, or rather a few reading lists.
1. For example have a fiction reading list, a self-help / mgmt reading list (if that's your thing), and then stuff that is specific to your domain. If you're into software engineering for example, you would likely have lots to catch up on in various areas: distributed systems, security, concurrency, networking, data structures, operating systems. It's fine to have a list in each area - but make it a really short list.
2. Curate the list. Especially for technical subjects, find those books which would help you learn faster and get to the next level. Be prepared to churn these lists, replacing some choices with others as you figure what works and what does not.
2. Devote some time each day, even if that's 30 minutes, to reading. Identify ahead of time what you would be reading. Make a couple of hours maybe during weekends and holidays, when you can.
3. Keep the books from your reading list close at hand.
4. By all means, catalog your e-books (and physical books too, but especially e-books) in an online catalog such as Goodreads or LibraryThing or some such. And then gawk at your own collection fishing for the next book ideas at least once every week.
1. This requires discipline - every time you download a book, you have to put an entry your online catalog. But then as Pythagoras once said, there's no royal road to geometry, nor to deep reading if I may add.

There is no reading without writing. Taking notes, and thinking about what you read make all the difference. Finding special interest groups / meetups in your locality that discuss what they are reading are a fantastic way to maximize your reading muscle.

Creating a body of work

This is perhaps the most important topic, and the one that requires maximum discipline. A body of work typically means a set of documents of some manner. This could be a set of academic papers, books or monographs, useful blog articles, instructional videos, significant long term contributions to one or more open source (or closed source) software, etc. or some combination thereof. It could even be photographs, paintings, performances as an actor or a musician or in some other performing art. However, here I would mostly focus on the former kind because this article lacks the space or the scope to talk about artistic creativity.

Your body of work is really a document of what you've built with your intellect. Instead of getting too prescriptive, I would like to focus on four aspects that are essential.

1. Have a vision of what purpose your body of work serves.
1. Maybe it teaches people difficult concepts in a simple way.
2. Maybe it reveals new insights about some subject.
3. Maybe it's an aid for other teachers, or researchers.
2. Identify the form-factor of your body of work.
1. Would it be a series of blog articles?
2. Would it be a book, or a book series?
3. Would it be code in a set of repositories?
3. Identify how would build that body of work.
1. Identify key concepts and notions, insights or even discoveries you've made, and start documenting them on an ad hoc basis.
2. Periodically collate your notes and documents, and start building rough drafts of your book / blog / video, whatever.
3. Publish, share with your consumers, and seek early feedback. Even when you want to directly earn money for your publications, this is still viable as lots of highly qualified people would happily read and review your work for free or for a small fee.
4. Make sure you are making progress on building this, every week, month, and year.
1. Progress can be slow, especially in the beginning. Speed (like in running, playing an instrument, or making money) is usually something you leave for later.

This is the undertaking that is the hardest to start on, but has the maximum bang for the buck. Having a vision, and having the discipline to pursue it are the key to achieving these goals.

Postscript

There are many other aspects that I haven't spoken of here. Building focus through mindfulness techniques, building a general outlook in life that is conducive to focus and attention (stoicism, anyone?), and the ability to think critically as well as pragmatically, are all vital ingredients of a solid knowledge career. The above article in some sense is more logistics, than principles. But hopefully the techniques give you a useful blueprint to follow.

Read more!

My mnemonics for the guitar / bass fretboard

Chord positions

For F-shape:

F G A B are frets 1, 3, 5, and 7, roughly speaking. These are the dotted frets.

C and D are frets 8 and 10, roughly speaking. These are the ones between the dotted ones.

E is fret 0 and fret 12.

For A-shape:

Bb C D E are frets 1, 3, 5, 7. These are the dotted frets.

F and G are frets 8 and 10.

A is fret 0 and fret 12.

For C-shape:

C D E are frets 1, 3, 5.

F, G, A are fets 6, 8, 10.

B is fret 0 and fret 12.

The C-shape is ahead of the A-shape by one full tone in position.

Identifying notes

For 1st and 6th string, we know that it is always the root note of the F shaped barre chord on that fret.

For 5th string, it is the root note of the A shaped barre chord on that fret. It is also the root note of the C-shaped chord that includes it.

For 4th string, it is the root note of the F-shaped barre chord that is barred two frets earlier.

For the 3rd string, it is the root note of the A-shared barre chord that is barred two frets earlier.

For the 2nd string, it is the note that is one full tone above the root note of the A-shaped barre chord on that fret.

Identifying the mediant, dominant, etc.

Now finding 3rd, 5th, and 7th notes.

- F-shaped and A-shaped chords are really the same structure, but the A-shaped ones are off by one string towards the higher pitch.

- The 6th string is not normally played in A-shaped barre chords.

- The 6th string, 1st string, and 4th string for F-shaped barre chords has the root note.

- For F-shaped chords, the 5th stirng (5 semi-tones behind the 4th string) has the 5th note.

- For F-shaped chords, 3rd string (4 semi-tones ahead of the 4th string) has the 3rd note.

- For A-shaped chords, the 4th string (5 semi-tones behind the 3rd string) has the 5th note.

- For A-shaped chords, the 2nd string (4 semi-tones ahead of the 3rd string) has the 3rd note.

Since we can find these notes based on the positions easily, we can immediately know the notes in the chord.

Chord relationships

This means that the root note of the F-shaped chord is the 5th note of the A-shaped chord barred at the same fret.

It also means that The 3rd note of the F-shaped chord is a flat of (one semi-tone below) the root note of the A-shaped chord barred at the same fret.

Read more!

Algorithmic problem solving: The importance of boundary values, edge case, and a consistent model

 I made the title sound almost like that of a computer science paper, although confessions here are of a more mundane nature. Using a small set of problems solving which I sucked at, I want to capture gaps in my own problem solving approach, and figure out patterns.

The right boundary conditions: Thief on a circular road

This is one of those famous problems. There is a circular road or whatever lined with houses. Each house has some cash. A thief is out thieving, but he cannot break into two adjacent houses on the same night as then some automated system notifies the police or dials 111 or some such (why does it need two adjacent houses to be broken into to raise an alarm is the question that perturbed me at a far deeper level all through the course of trying to solve the problem, but ...). The actual problem isn't all that hard to solve. But we have some interesting boundary conditions. If there are no houses, the maximum loot is 0. When there is exactly one house, the maximum loot is the money in that house. When there are two, the maximum loot is the higher of the sums in the two houses. The general algorithm starts being applicable starting with three or more houses. Stated this way it sounds simple, but writing it cleanly is important. It is also worth spending a tiny bit of time trying to keep these special cases as general as possible, but more often that not it doesn't work.

Defining structure: Finding zero-sum triplets in an array of integers

Given an array of integers, find unique triplets that sum to zero. Obviously this won't happen in an array that does have a mix of integers of opposite signs (or one having all zeros). The harder part is to get unique triplets out without any sort of post-processing.

First shot

Without the unique constraint, here was my flawed first shot. We sort the array, and loop through it one element at a time. For each element, we look for two other elements that sum to its negative - and we shall have our triplet. Obviously, we have reduced the problem of finding a triplet to a slightly easier problem of finding a pair of elements matching a constraint. We start by summing two elements one from each end. If their sum is less than the target, we pick the next higher element from the left. If the sum exceeds the target, we pick the next lower element from the right. Else we have our triplet. This is good but inadequate - it does not eliminate duplicates.

Dedup, initial thoughts

One possible way we would be to start with a sorted array of unique elements. But this means we modify the input or make a copy. However, even that alone won't be enough. A little thinking leads us to the observation that if I found a triplet from elements at positions i, j, and k in the sorted array, then I would hit this triplet thrice - first time when I picked a[i] and looked for a pair summing to -a[i], second time when I picked a[j], etc. and third time when I picked a[k]. So if we pick a[0], and look for a pair with a matching sum of opposite sign, then we should exclude a[0] from further searches because we would have found any pairs with a matching sum of opposite sign already. This means, starting with a[i], we should always search for j and k such that j > i and of course k < size.

Dedup, the comprehensive way

The above would suffice in a sorted array of unique elements. But if we want to avoid that chore and keep the input read-only or avoid copying, we can still do it. Simply put, if an element is repeated then we should skip all copies of it after the first. If a[1] equal a[0], we should just skip the logic for a[1]. If a[j+1] equals a[j], we again skip the logic for a[j+1] and so on.

None of these ideas are difficult, but they need a bit of thinking about the structure of the array - for most people perhaps.

Establishing the above structures is important - like shrinking the search space in each successive iteration, and skipping over duplicates.

Read more!

A smattering of bitwisdom

I remember my epiphany about bit-twiddling. It was one small insight - the fact that 1 in binary is the equivalent of both 1 and 9 in decimal, but more often than not (to speak very facetiously) the latter. So 1111 is like 9999 in the sense that adding 1 to either will result in 10000, in the respective bases. Of course, binary 1 is equivalent to decimal 1 as well, because you add 1 to 9999 (or 1111) and get 10000. Also, subtracting 1 from 10000 has the predictably opposite effect of producing 1111 or 9999 as the base may be (pun intended).

Turning off bits and counting bits

This has several interesting consequences that are often used in bit-wise computations. For one, if the lowest n bits of x are 0, then x-1 would turn them into 1, and the n+1th bit, i.e. the lowest significant bit, to 0. What this in turn would mean is that x & (x-1) would simply turn off the lowest significant bit. We could use this successively on a number to turn off each of its significant bits, and count how many it takes till the number is reduced to zero - basically giving us a quick way to count set bits in a number.

Setting bits and bit ranges

Again, x+1 also does some stuff. Just as x-1 unsets the least significant bit, x+1 sets the lowest zero bit (and unsets all lower bits). So if the lowest n bits of x are set, and n+1th bit is 0, then x+1 unsets all these n bits, and sets the n+1th bit. This means repeated application of x |= (x+1) would set all its bits. But when does one stop? At some point all the bits of x up to its most significant bit are set. At this point, if we perform x & (x+1), we would get 0. So that should be the condition to check at each iteration.

The point of this post ... a leetcode medium problem

So far, I have repeated what is common knowledge. What's the point of this post then? I came across this leetcode problem - how to compute the bitwise-and of a continuous range of integers - could be the entire range of 32 bit positive signed integers.

I liked this problem because it didn't immediately fit a pattern, and I had to think about it. Now, it's useful to remember here that the nth power of two has a binary representation of 1 followed by n 0s. That means if we bitwise-and a range of numbers, the smallest of which is less than 2^n and the largest of which is greater than 2^n, then 2^n will occur in that range and nullify all the numbers resulting in 0 (think why). So only a range that lies entirely between two successive powers of 2 could yield a non-zero bitwise-and. At this point it's relatively straightforward to figure out the rest. Here is the logic:

If the range is [a, b], find the maximum power of 2 in the a and in b. If they aren't equal, the result would be 0, so return. Else, assuming that power is 2^n, set the n+1th bit in the result. Then repeat the process for a-2^n and b-2^n.

Read more!

Merry ways of Binary Search

Binary search is an extremely important algorithmic technique in the armory of all programmers. It isn't typically thought of as an advanced algorithm, yet is deceptively simple, and features a few nuances to be aware of. In its simplest form, binary search tries to find a matching element from a sorted array of elements. I specifically said array, and not list, because the elements have to be contiguously stored and randomly accessible by index for binary search's O(log N) time-bound to hold.

To perform binary search, we usually define a condition that would be satisfied by some prefix of the array (could be of length zero) and not satisfied by the remaining array. This condition divides the array into two parts, and informs our algorithm which part could be discarded in the next step, thus reducing the search domain and zeroing in on a matching element if one exists. Below is a simple binary search implementation that works.

int binary_search(const vector<int>& nums, int key) {
  int low = 0, high = num.size() - 1;
  while (low < high) {
    int mid = low + (high - low)/2;

    if (nums[mid] < key) {
      // discard the left part
      low = mid + 1;
    } else if (nums[mid] > key) {
      // discard the right part
      high = mid - 1;
    } else {
      return mid; // we found a key
    }
  }
  return -1;  // we didn't find the key
}

The above implementation is about as simple as things can get. In most applications, we end up doing more with binary search. Let's modify the above problem slightly, to that of finding the location where the key would be inserted if it isn't already present - arguably a more useful variant. We really have to change what we return when we don't find a matching value:

  return low;  // or high
}

Quick summary

What's the key insight into binary search?

The first is that it's binary, meaning we divide the sorted array into two mutually exclusive sections. One section includes the target element if present, the other section decidedly doesn't.

The second is that we compute the mid-point of the array and check if it sits in the section that might include the target, or the one that doesn't. If it doesn't include the target, we update one end of the search space to exclude the mid-point, i.e one end becomes right = mid-1 or left = mid+1 as the case maybe. If on the other hand, the mid point is in the section that may include the target, then we update one end of the search space to point to the mid-point - we don't exclude it. So it becomes left = mid or right = mid as the case may be. This process continues until left and right converge inside the inclusive section, right at its boundary.

Finally, an important implementation note which can help. We can compute the mid-point in one of two ways:

   mid = left + (right - left)/2;

   mid = right - (right - left)/2;

When left and right are right next to each other, mid equals left in the first case, and right in the second case. Which form should be used depends on which update rule was used before that. If left was set equal to mid earlier, then the first form would repeatedly result in mid remaining at the same value and causing an infinite loop. If right was set equal to mid earlier, the same problem would appear with the second form.

So if we set mid = left, then use the second form, and if we set mid = right, then use the first form. It doesn't make a difference for update rules that add or subtract 1 on mid.

Finding ranges

Now, imagine that there can be repeated elements, and we'd like to find the first position where a repeated element occurs, as well as the last position. We can always run the regular binary search to find some occurrence of the element, and then do linear search backward or forward to find the first or the last matching element. But, this makes an O(log N) algorithm into a worst-case linear algorithm. There must be a better way.

One way to think about it is to observe that the first matching element in the array occurs at the border of a prefix for which nums[i] < key, and a second region for which nums[i] >= key. We are looking for the first element of the second region. This means that our search domain should always include this boundary.

We quickly modify our code above.

int find_first_of(const vector<int>& nums, int key) {
  int low = 0, high = nums.size() - 1;
  while (low < high) {
    int mid = low + (high - low)/2;

    if (nums[mid] < key) {
      // discard the left part
      low = mid + 1;
    } else { // nums[mid] >= key
      // discard the right part
      high = mid;
    }
  }
  return low;  // we didn't find the key
}

Notice the slight modifications. We no longer check specifically for equality. Instead we try to ensure that the remaining search domain after each step includes the boundary and zeroes in on the first element after the boundary. This is all good. What if we wanted to return the last element instead? Can't be too different, can it? Well in this case, the search domain must include the boundary between elements less than or equal to the target, and elements greater than the target.

int find_last_of(const vector<int>& nums, int key) {
  int low = 0, high = nums.size() - 1;
  while (low < high) {
    int mid = low + (high - low)/2;

    if (nums[mid] <= key) {
      // discard the left part
      low = mid;
    } else { // nums[mid] > key
      // discard the right part
      high = mid-1;
    }
  }
  return low;  // we didn't find the key
}

The update rules changed slightly, but guess what - the above code doesn't work. It goes into an infinite loop! The reason is that mid is computed as low+(high-low)/2, but when low and high are next to each other, i.e. the range is only two elements, then (high-low)/2 is 0, and so mid equals low. This means in successive iterations, the value of low doesn't change when ideally it should converge to high. Why hasn't this hit us so far? Notice that in the earlier examples, we never assigned mid to low, like we did here. What's the solution? Well, there is no mid for a two-element range. So use mid=high-(high-low)/2. This will mean that mid would become equal to high eventually. Since we assign mid to low, eventually low and high would converge. Conversely, if we used this way of computing mid in find_first_of, that one would go into an infinite loop.

Searching in a rotated array

An array is said to be rotated by k positions, if the original elements of the array have been shifted by k index positions. And spillover elements wrap around from zero, hence called rotation. If an array is sorted but rotated, and we don't know by how much, can binary search be of any help? For that matter, can binary search determine the amount of rotation? Turns out that it can, without much need to resort to anything linear.

If a sorted array is rotated, then the largest and smallest elements would be neighbours somewhere in the array. How do we find this location? In an array with a large number of duplicates, this might be tricky to do. But in an array with unique elements this is simple. In the rotated array, the beginning would be larger than the end, and the max element would lie somewhere between the beginning and the end, either in the first half, or in the second half. We call this the pivot point, and following is the code to find it.

int find_pivot(vector<int> nums) {
  int low = 0, high = nums.size()-1;

  while (low < high) {
    int mid = high - (high-low)/2;

    if (nums[low] < nums[mid]) {
      low = mid;
    } else {
      high = mid-1;
    }
  }
  return low;
}

Notice how we use the appropriate form for calculating mid, based on the update rules - to prevent infinite loops. This would terminate and return the position of the largest element.

Searching an element in the rotated array is also similar, and requires just a few changes, as shown below.

int find_elem_in_rotated(vector<int> nums, int key) {
  int low = 0, high = nums.size()-1;

  while (low < high) {
    int mid = high - (high-low)/2;

    if (nums[low] < nums[mid]) {
      if (nums[low] <= key && key < nums[mid]) {
        high = mid - 1;
      } else {
        low = mid;
      }
    } else {
      if (nums[mid] <= key && key <= nums[high]) {
        low = mid;
      } else {
        high = mid - 1;
      }
    }
  }
  return low;
}

This would return the location of the key if present, or the position where it can be inserted, if not present.

Read more!

vim as an IDE for C++

I found a relatively quick way to setup vim / neovim as an IDE for C++. Here is how it works.

1. vim loads a plugin called Coc (I pronounce it coque which is a family-friendly approach).
2. Coc runs a nodejs process to perform runtime checks.
3. This process starts a configured language server (such as ccls or clangd) and then communicates with it.

 Here is what we need to set it up.

1. Install ccls.
   
2. Configure ccls by using a .ccls file at the root of the project, or by generating a compile_commands.json file as with the set(CMAKE_EXPORT_COMPILE_COMMANDS on) option.
3. Install a relatively new version of nodejs (I installed 16.14.0 LTS).
1. curl -sL https://deb.nodesource.com/setup_16.x -o nodesource_setup.sh
2. sudo bash nodesource_setup.sh
3. sudo apt install nodejs
   
4. Install the Plug plugin management system in vim.
1. curl -fLo ~/.vim/autoload/plug.vim --create-dirs https://raw.githubusercontent.com/junegunn/vim-plug/master/plug.vim
5. Edit .vimrc to add the neoclide/coc plugin, the long list of key bindings from coc for convenience, and then reopen vim, running the command :PlugInstall.
6. Configure coc using :CocConfig and editing the JSON that shows up. Refer here.
7. Open a C++ source file in your project in vim / neovim.
   

Read more!

Explorations of a wannabe security programmer

 Right now I am in that state where I am trying to make sense of different security building blocks, and feeling for the true use cases they help solve. This has been an interesting journey because it builds understanding of problems as well as perspective. The uber-perspective is that security is never really a fully-solved problem. Getting the basic interactions and workflows right is merely the beginning. There are many scenarios and edge cases to take care of when dealing with real production deployments, and there are a ton of concerns around hardening the security of such a deployment. It's a game of probabilities, and therefore of prioritization.

HashiCorp Vault

HashiCorp Vault has been at the top of my list of technologies to understand for a while now. That's not only because it seems like a particularly good component to build a cloud-agnostic architecture around, which it is. It's also because of how well it helps address security concerns that often do not figure in the architect's priority list till the security team comes back and either vetoes the release or does some hard-talking to extract commitment for a vulnerability fix patch.

What I figured while trying to learn Vault is that it isn't straightforward, and while there is plenty of documentation, what is lacking is a good cohesive introduction that shows the big picture well. I thought I'd jot down, still rather tersely, my understanding of what Vault essentially is and does.

HashiCorp Vault is a service that you run in your deployment, and which stores and protects your secrets from unauthorized access, credential theft, and proliferation of secrets.

1. It stores secrets securely, ensuring secrets are always encrypted, whether at rest or in transit.
2. It allows only authorized access to these secrets.
3. Easy access management through policies
4. Integrates with a wide number of applications, databases, continuous integration systems, container orchestrators, etc.
5. Recommends ways to secure deployments from the outset.

The last point, which HashiCorp calls the Secure Introduction problem is significant. Essentially, it tries to answer the following question.

When a new component (a service, container, VM, etc.) is introduced into a system, how do existing components authenticate it? In essence, it is the problem of establishing trust where none exists to begin with, and needless to say, it relies on some best practices rather than any innovative technique to get the job done.

How does Vault work

Vault works through a set of abstractions for creation, retrieval and management of secrets. Here are the key abstractions.

1. Storage engine: The storage backend used to store the secrets securely. This could be local disk, a cloud-based key management system such as Azure Vault or AWS KMS, HashiCorp Consul, etcd, etc. This is part of the server start-up configuration.
2. Secrets engine: The secrets engine defines the type of secret that is protected, as well as the kind of metadata associated with a secret, and the operations that can be performed on it. For example, these could be static key-value pairs, database credentials, etc. Secrets and their associated metadata can be stored and retrieved using a path-based naming scheme of the form: <engine>/<path>/<secret-id>.
3. Sealing and unsealing: When a Vault server bootstraps, it does so in a sealed mode (except when you run it in dev mode which is obviously only for development). Sealed mode means that the Vault server has no way to retrieve and decrypt keys stored in its storage backend. It must be unsealed to begin operations. Vault uses a master key to unseal itself and generates this key during initial configuration. But it goes a step ahead and shards that key into N participant keys, any M (<=N) of which are required to unseal it. The idea is that these N keys would be with N different individual admins, M of whom must enter the key at the time of unsealing. Also, the Vault can be sealed back by using just any one of these N keys. The algorithm to shard the master key into M keys is called Shamir's Secret Sharing algorithm.
4. Authentication backends: Vault integrates with several authentication backends, including a plan user/pass backend, LDAP and ActiveDirectory, and many others. This is used for authenticating clients of Vault that want to access secrets protected by Vault.
5. Tokens: Tokens are strings that are used to access the actual credentials (such as usernames and passwords). They have limited validity (TTL) and limited renewability. Each token may have any number of policies associated with them which determine what can be accessed using the token. Depending on the secrets engine, the actual credentials are generated only when a user requests them using a token, and are revoked when the token expires.
1. Root tokens:
2. Token hierarchies:
3. Cubbyhole tokens: Cubbyhole tokens are special key-value pairs in which there is a wrapping token and a wrapped token. The wrapping token can only be used twice: first to store the wrapped token, and then to retrieve it. On retrieval, the wrapping token expires and the wrapped token is retrieved. This is useful for generating one time use passwords that need to be securely retrieved.
6. Policies: A policy consists of a secret path and associated privileges (such as read, write, create, update, get, list, etc.). A token can be used to access secrets from all paths that associated policies grant access to.

This is blog post is a work in progress. Expect more details to be added.

Read more!

The struggles of a wannabe security programmer

 Yeah, I'm impressed that I have been able to sort of grok what goes by the name OAuth2.0 and its bastard child OpenID Connect or OIDC. And can at least make sense of a conversation on SAML. That in itself is no mean feat, frankly. YouTube was quite helpful at that, which is a rarity in my case. But what to do beyond that? I want to try this stuff with my own hands and I am frankly out of depth here. I have a laptop or two where I can set stuff up and tinker with things. How do I get started?

Maybe auth0 is the place? Or maybe ory/hydra + ory/kratos? Could it be dex? But they can't write a paragraph without talking about kubernetes! Maybe the do-it-all grand daddy of the trade - Shibboleth? Or the really cool Authelia? How about caddy-auth-portal.

There lies the problem. There's plenty to grok on the topic, all of it in the open source. But almost everything is so hostile to a beginner that unless you're ready to read code and try all kinds of google searches, and YouTube videos and piece together a picture for yourself, nothing will let you get to the heart of it and build an understanding by doing stuff in an isolated environment with minimal dependencies. Yeah, I hate it when you start talking about how to run this thing with docker or docker-compose without bothering to write a paragraph about the architecture and dependencies. But such is true open source these days. If you aren't doing this, you aren't doing it right I guess. The thing is, good man pages and documentation go a long, long way to building understanding. It seems that they are also incredibly hard, because making your writing useful (as opposed to merely legible) requires empathy.

Yeah, ranting! But ok, what are my key takeaways on OAuth2.0 and OIDC?

1. It's complicated. You can still grok it.
2. Ultimately, it is a mechanism for granting a time-bound token (the access token) to an application (the client app) to access protected information (the resource).
1. In general, the token can be used to query a defined set of data from a protected service (called the resource server). This means the token is only good for accessing data it was supposed to be used for and not have an unrestrained access on the resource server.
2. In the case of OIDC, that protected information is actually information about a user who has been authenticated by the process. Basic info is available as a second token, a JWT token called the ID token. For additional info, you 
3. How does it work? Through a system of redirects.
1. The center of all action is the client app. If it is unable to figure out the access tokens to use, it redirects to an authorization server, which protects access to the resource server.
2. Now obviously, it is the user (called the resource owner) who can authorize the request. They do so by:
1. Authenticating themselves at the authorization server.
2. Consenting to allowing access to specific resources (referred to as scope) on the resource server.
3. When the above process completes, the authorization server redirects the request back to the client app with an authorization key and some other identifiers. This authorization key allows the client to initiate interaction with the resource server, on behalf of the resource owner.
4. You'd have thought that this is the end of the story. But not really. This key just allows the client app to initiate communication, but to continue it, the client app must get an access token in exchange of this auth key. This is where the details we so far overlooked start to matter.
1. How does the auth server know which client app URL to redirect to?
   Actually, each client app must individually pre-register with the authorization server. When they do this, they get a client identifier, and a client secret. These are sent as part of the initial redirect to the authorization server.
2. Why does the auth server issue an access token to the client app only after getting the authorization key from the client?
   The authorization server keeps track of each authorization key it issues and the client it issues it for. Assuming that the client is not compromised, it only trusts a request carrying this authorization server which also carries the correct client id and client secret. That's when it responds directly to the client with the more durable access token.

There is no public key exchange / certificate signing that happens between the resource server and the client app so that they could trust each other via mTLS. Instead the trust is mediated by the resource owner who gives consent to the interaction. But the resource server isn't going to trust any arbitrary caller just on the basis of the resource owner's consent. That's why:

1. The client app must independently register itself with the authorization server, and obtain its identifiers.
2. When the resource owner consents to the request from the client app, the authorization server verifies that this is a client they know before issuing the initial authorization code. This wouldn't be possible without step 1.
3. And finally, the authorization key it sends back to the client app via redirection must come back to it from the same client before it can allow the client to begin a trusted communication with the resource server.

Obvious questions would be:

1. What does the client do as part of the registration with the authorization server?
2. How does the resource owner validate the access token in each request from a client?
3. How does the resource server authorize the request carrying the access token?

I have some idea about these but I will add them here when I know better.

There are actually several flows defined by OAuth 2.0 and the one described above is the Authorization Code flow or simply code flow. There is also an implicit flow which is less secure - which sends the access token to the client app directly instead of sending a temporary auth code first. The OIDC flow likewise is different.

PS. By the way, I forgot to mention that I do have something of an idea about how to try this hands-on. I will go with dex, and try setting up an LDAP authentication server on Linux, then point dex to it. At least that will be a start.

Read more!

Out of touch with C++, and other new stuff

MongoDB is quite cool. Apart from being written in C++, it's a document DB (one that can store and index JSON / JSON-like content) in a distributed database that supports sharding, replication, and eventual consistency. You can run it as a single server too, which is useful for writing application code that connects to it.

1. The server is called mongod.
2. There is a REPL client / interpreter called mongo which also happens to be a full-fledged JavaScript interpreter.
3. A single Mongo instance can host multiple databases, each stored in its own file.
4. Each database can have multiple collections. analogous to tables in an RDBMS.
5. Each collection has zero or more documents, corresponding to rows in RDBMS but the similarities are faint.
1. A document is a JSON or JSON-like content. JSON-like refers to the fact that there are extensions to the JSON-format supported - with value types like Date, binary, etc. being supported.
2. Every document has a unique identifier - the _id attribute, which must be unique in a collection. It's default type is ObjectId, which is a 12-byte integer, but can be any type. The 12-byte integer is partitioned from left to right as "4[epoch seconds]|3[hostname hash]|2[pid]|3[incr num]".

The main meat of the topics are perhaps in dealing with distributed data - sharding, indexing, consistency, and all the tools used to implement these. There are also specifics like expression languages for queries, as well as client libraries. There are also many specifics about working using the mongo REPL. Last, but not nearly the least, is the topic of building applications using Mongo - a topic that influences how application data is expressed via Mongo, and consumed from it. More on that in another post.

C++ has been an old love affair, a fact that alienates me from a lot of well-meaning programmers at the outset, and endears me to a few. But truth be told I have not written a lot of C++ over the past few years and have grown my own contrarian opinions about the usefulness of many recent additions to the language. I didn't get a chance to work with fold expressions earlier but looked at it recently.

To me fold expressions appear to be a syntactic convenience for unrolling loops involving parameter packs without explicitly writing the templates and their specialization needed before. The code does become shorter, but does it really become more expressive? I don't know - I think it becomes a little cryptic / terse because the syntax doesn't intuitively express what's happening. You have to know and get used to it, like with parameter pack expansions involving function and template expressions.

I don't have much to argue on the matter. The C++ folks can always shut me up by saying that this is a tool for library writers that people like me can ignore. Maybe they are right. But I do wonder, why library writers have to put up with cryptic syntax. Isn't simplicity of value to them?

Read more!

Recent pitfalls at work

Spent unproductive hours debugging issues that should have taken less time. Why?

1. I implemented something without experimenting enough, based on dodgy documentation (in fact no good documentation is available).
2. An oversight in my analysis / design. I got away with a small fix but sometimes this can be costly.
3. Didn't check if my code ran on all environments it was targeted at. For example, I introduced a dependency on OpenSSL without verifying if it can be fulfilled everywhere.

 #1 is easy to address. Run more small experiments as a habit while building software. I do blame the dodgy doc too. I eventually ran the experiments and it took some effort to be honest.

#3 should be done better as a habit. Listing assumptions and environment requirements explicitly while making them should be a good start.

#2 was disappointing because I pride myself on design thinking. It was a small detail that I missed through oversight. The way to catch this early would be to deliberately list all preconditions.

Read more!

Enable autocomplete for C++ on vim

 Assuming you have a recent version of vim (8.1 should do) this is a lot easier now.

1. If you don't already have Vundle:
   git clone https://github.com/VundleVim/Vundle.vim.git ~/.vim/bundle/Vundle.vim
2. Add the following section to ~/.vimrc. The vundle section may already be there in which case you just add the Plugin line for Valloric/YouCompleteMe.
   set rtp+=~/.vim/bundle/Vundle.vim
   call vundle#begin()
   Plugin 'VundleVim/Vundle.vim'
   Plugin 'Valloric/YouCompleteMe'
   call vundle#end()
3. Clone YouCompleteMe.
   git clone https://github.com/Valloric/YouCompleteMe.git ~/.vim/bundle/YouCompleteMe
4. Update YouCompleteMe.
   cd ~/.vim/bundle/YouCompleteMe && git submodule update --init --recursive
   
5. Install the clang completer. This works but a better way may be to configure clangd.
   ./install.py --clang-completer
   
6. Add a file .ycm_extra_conf.py to some ancestor directory of your C++ projects.
   def Settings( **kwargs ):
     return {
       'flags': [ '-x', 'c++', '-Wall', '-Wextra', '-Werror' ],
     }
   
   There are other ways of doing the above that can give you more flexibility in your own sandbox. You can check them here: https://github.com/ycm-core/YouCompleteMe#general-semantic-completion

Read more!

Algorithms: Two interesting problem solving techniques

I recently learned two interesting techniques for solving problems using algorithms that could be called non-obvious and ingenious. But I think there is a pattern to it that is worth recognizing, and hence this post. These problems are courtesy one or the other of the several good online platforms for practicing algorithmic problems. The code is mine.

Using BFS to solve a dynamic programming problem

(This section is identical to my quora answer: https://www.quora.com/Is-the-breadth-first-search-an-example-of-dynamic-programming)

Let's look at the first problem: You have N oranges. On any given day, you can decide to eat a certain number. This can always be 1. But if you have an even number of oranges, you can eat N/2. If the number of oranges you have is divisible by 3, you can instead eat 2N/3 if you want. What is the minimum number of days in which all the oranges can be eaten?

This problem is definitive of typical dynamic programming problems and there is a fairly routine dynamic programming solution to this problem. Here goes the dynamic programming solution first.

int minDays(int n) { 
    std::vector<int> minDays(n+1); 
    // minDays[n] == min days for n oranges 
 
    minDays[0] = 0; 
 
    for (int i = 1; i <= n; ++i) { 
        int minDay = 1 + minDays[i-1]; 
        if (i % 3 == 0) { 
            minDay = std::min(minDay, 1+minDays[i/3]); 
        } 
        if (i % 2 == 0) { 
            minDay = std::min(minDay, 1+minDays[i/2]); 
        } 
        minDays[i] = minDay; 
    } 
    return minDays[n]; 
} 

This is an O(n) algorithm. But turns out that we can do much better. Consider N=12. On the first day, you could eat 8 oranges, or 6 oranges, or just 1. So there are three different paths you code take. For each of those there would be one, two, or three choices to make on the second day. This is also the classic dynamic programming structure but, it is also a graph. By traversing through this graph breadth-first, it is possible to evaluate these paths and figure out the first path to reach zero - the fastest to zero oranges. The following is a BFS solution.

int minDays(int n) { 
    if (n <= 0) { 
        return 0; 
    } 
 
    std::queue<int> bfsQueue; 
    std::set<int> seen; 
    bfsQueue.push(n); 
    int days = 0; 
         
    while (!bfsQueue.empty()) { 
        int size = bfsQueue.size(); 
         
        for (int i = 0; i < size; ++i) { 
            int entry = bfsQueue.front(); 
            if (entry == 0) {  
                return days; 
            }    
                     
            bfsQueue.pop(); 
 
            auto it = seen.insert(entry); 
            if (!it.second) { 
                continue;  
            }    
                     
            // push the child entries 
            if (entry % 3 == 0) { 
                bfsQueue.push(entry/3); 
            }    
            if (entry % 2 == 0) { 
                bfsQueue.push(entry/2); 
            }    
            bfsQueue.push(entry-1); 
        }        
        days += 1; 
    }        
    return days;  
} 

I don’t have a complexity number for this. Had the child nodes been all distinct, the complexity would possibly have been O((3k)^d) for some constant k less than 1, where d is the minimum number of days required. This itself grows much faster than O(n). But the fact that many of the child nodes are actually the same - the overlapping sub-problems property of dynamic programming - possibly makes this O(d*log(n)) or something like that. And I could be way off the mark here - I am just speaking from observation and some very rudimentary reasoning.

Using binary search in an optimization problem

Here goes the second problem: You are given a list of positions on a straight-line where you can place magnets. The attraction between the magnets is inversely proportional to the distance between them. You are given m magnets and want to minimize the maximum possible attraction between any two magnets when you arrange them. That is same as saying that you want to maximize the minimum distance between two successive magnets.

The given positions are a constraint. Discounting that for a minute, if you had four magnets that you could place anywhere between positions 1 and 10, how would you do it?

 First magnet at 1, last magnet at 10 - that's a given. The second magnet could be at 4, the third at 7. That would make the minimum distance between any two magnets to be 3. You cannot have any arrangement of four magnets at positions 1-10, in which the smallest distance between two magnets (obviously successive) is 4. Now how on earth does one solve this. I thought of dynamic programming initially but couldn't frame it as one - maybe it is possible to solve it that way. But if the range of positions is 1 through 10, and there are 4 elements, the elements an equitable distribution of 4 elements would require a distance of maximum (10-1)/(4-1) = 3 between two successive elements. Therefore the minimum distance between two elements can never be more than 3. And of course, the least distance is when they are next to each other - i.e. 1. This means, what we are trying to find out is really whether it is possible to place the elements with a minimum distance of x between them where 1 <= x <= 3. Of course, instead of 1 <= x <= 3, the range could be arbitrarily large, say 1 <= x <= 1000000. And that's where you're gonna have to search that state space using something better than a linear algorithm starting from 1 through 1000000 (or the other way). Now if it be possible to place elements with a minimum distance of x, then it goes without saying that it is possible to do so for all [1, x]. So then we are interested to find if it is also possible to do so for some x' in (x, 1000000]. So by making minor modifications to the binary search process we can find the largest x satisfying our constraint. Here goes the code.

 

    int maxDistance(vector<int>& position, int m) {
        if (position.empty() || m <= 1 || position.size() < m) {
            return 0;
        }
        std::sort(position.begin(), position.end());
        int first = position.front(), last = position.back();
        if (m == 2) {
            return last - first;
        }

        int max_gap = (last - first)/(m-1);
        int min_gap = 1;
        int max_min_gap = -1;
       
        while (min_gap <= max_gap) {
            auto cur_gap = min_gap + (max_gap - min_gap)/2;
            if (!canFitWithMinGap(position, m, cur_gap)) {
                max_gap = cur_gap - 1;
            } else {
                max_min_gap = cur_gap;
                min_gap = cur_gap + 1;
            }
        }
        return max_min_gap;
    }
   
    bool canFitWithMinGap(const vector<int>& position, int num_elems, int gap) {       
        auto begin = position.begin();
        auto start = *begin;
        int last = position.back();
        for (int i = 0; i < num_elems - 2; ++i) {
            begin = std::lower_bound(begin, position.end(), start + gap);
            if (begin == position.end() || (last - *begin) < gap) {
                return false;
            }
            start = *begin;
        }
        return true;
    }

The idea is simple but it takes a bit of thinking to see this as a viable approach.

Read more!