Wednesday, August 30, 2023

Timeouts In Envoy

Just a quick summary post. Envoy allows configuring various timeouts that allow tweaking the behavior of HTTP as well as general TCP traffic. Here is a summary of a few common ones. 

Why am I writing this? Like with a lot of Envoy documentation, all of this is documented, but not in a shape that is easy and quick to grok. Note that you need to understand Envoy and the structure of its configuration to fully understand some of the details referred to, but you can form an idea even without it if you understand TCP and HTTP in general.

There are chiefly three kinds of timeouts:

  1. Connection timeout: how long does it take to establish a connection?
  2. Idle timeout: how long does the connection exist without activity?
  3. Max duration: after how long is the connection broken irrespective of whether it is active or not? This is often disabled by default.

These often apply reasonably to both downstream and upstream connections, and configured appropriately either under a listener (in HTTP Connection Manager or TCP proxy) or in a cluster.

Connection timeouts

How long does it take to establish a connection?

This is a general scenario which can apply to either plain TCP or HTTP connection. There is also an HTTP analog in the form of stream timeout or the time it takes to establish an HTTP/2 or HTTP/3 stream.

A very HTTP-specific timeout is: How long would the proxy wait for an upstream to start responding after completely sending an HTTP request to it?

This is called a route timeout, that is set at the route level, and defaults to 15s. It can of course be overridden for individual routes.

Idle timeouts

How long can a connection stay idle without traffic in either direction?

Again, a general scenario that could apply to either plain TCP or HTTP connections. With HTTP/2 and above, idleness would require no active streams for a certain period. There is also an HTTP analog for streams in the form of an idle timeout for individual streams. These can also be overridden at the HTTP route level.

Here is another one. How long should a connection from the proxy to an upstream remain intact if there are no corresponding connections from a downstream to the proxy?

This is called TCP protocol idle timeout and is only available for plain TCP and is in fact a variation of the idle timeout.

Max duration

How long can a connection remain established at all, irrespective of whether there is traffic or not? This is normally disabled by default. It is not available for plain TCP, only for HTTP. Even when enabled, if there are active streams, those are drained before the connections is terminated. May be useful in certain situations when we want to avoid stickiness, or upstream addresses have changed and need reconnection without the older endpoints going away. There is an HTTP analog for maximum stream duration. These can also be overridden at the HTTP route level.

There are a few other timeouts with specific uses available, but the above is a good summary.



Read more!

Friday, August 25, 2023

All about JWKS or JSON Webb Key Sets

What are JSON Web Key Sets?

Refer to this too to understand how it looks: https://auth0.com/docs/secure/tokens/json-web-tokens/json-web-key-set-properties

In addition, refer to this: https://redthunder.blog/2017/06/08/jwts-jwks-kids-x5ts-oh-my/.

Besides, here are some handy commands.

First up, to get the public key from the cert, run:

openssl x509 -pubkey -noout -in <cert_file>

To generate the value of n, run:

openssl rsa -pubin -modulus -noout < public.key

Finallly to get the exponent (e), run:

openssl rsa -pubin -inform PEM -text -noout < public.key

The kid field needs to be some value that uniquely identifies which key was used for encryption. x5t is SHA-1 thumbprint of the leaf cert but is optional and can be skipped.

What good are they?

They are used to put together multiple cert bundles, which could be used to validate auth tokens such as JWS tokens. Many systems including Envoy takes the bundle in JWKS format, and this also works well with SPIFFE/SPIRE type systems.



Read more!

Sunday, June 11, 2023

Configuring Calico CNI with VPP Dataplane for Kubernetes

This is a quick run-down of how to configure Calico for pod networking in a Kubernetes cluster. Calico comes in several flavors, and we look at Calico with the VPP data plane, as opposed to classic Calico. One reason for looking at this option is to be able to use encryption at the L2 layer using IPsec, which is supported by VPP but not classic Calico.

Installing Kubernetes

This article doesn't cover how to install Kubernetes - there are several guides for doing that, including this one. Once you have installed Kubernetes on your cluster nodes, and the nodes have all joined the cluster, it is time to install the CNI plugin to allow pods to communicate across nodes. However, there are a few things that need to be ensured even while configuring Kubernetes, before we actually get to installing the CNI plugin.

Calico by default uses the subnet 192.168.0.0/16 for the pod network. It's good to use this default if you can, but if you cannot, choose the subnet you want to use. Then set Kubernetes up with the alternative CIDR you have in mind. If you use kubeadm to set up Kubernetes, then use the --pod-network-cidr command-line option to specify this CIDR. Here is an example command-line to do this on the (first) master node:

    kubeadm init --apiserver-advertise-address=10.20.0.7 --control-plane-endpoint=10.20.0.7:6443 --pod-network-cidr=172.31.0.0/16

The output of this command would contain the kubeadm command-line to run on the other nodes to register them with the master. At this point, running kubectl get nodes would list the cluster nodes but they would be shown in the NotReady state. To change that, we would need to install Calico.

Installing Calico

The page here already summarizes the process of installing Calico with VPP quite well, but there are a few things that need to be called out.

Hugepages and vfio-pci

This step is required only if you want to choose a specific VPP driver that would be used to drive the physical interface, namely virtio, dpdk, rdma, vmxnet3 (VMware), or avf (certain Intel drivers). If this is not explicitly chosen but left to the default, even then these settings can improve performance, but the memory requirements would typically be higher per node.

On each cluster node, create a file called /etc/sysctl.d/calico.conf and add the following content.

vm_nr.hugepages = 512

Then run:

    sudo sysctl -p

Similarly, on each cluster node create a file call /etc/modules-load.d/calico-vfio-pci.conf, and put the following content line it.

vfio-pci

On CentOS / RedHat, this should be vfio_pci instead. Then run:

    modprobe vfio-pci   # or vfio_pci on CentOS / RedHat

Finally, reboot the node.

Customizing the installation config

Create the Tigera operator:

    kubectl create -f https://raw.githubusercontent.com/projectcalico/calico/v3.24.6/manifests/tigera-operator.yaml

Download the installation-default.yaml file and modify it as suggested below:

    wget https://raw.githubusercontent.com/projectcalico/vpp-dataplane/v3.24.0/yaml/calico/installation-default.yaml

In this file, there would be two objects listed. An Installation object, and an APIServer object. We would only edit the manifest of the first. Under the spec.calicoNetwork sub-object of Installation, add the ipPools attribute as shown below:

spec:
  calicoNetwork:
    linuxDataplane: VPP
    ipPools:
    - cidr: 172.31.0.0/16    # or whatever you chose for your pod network CIDR
      encapsulation: VXLAN   # or IPIP
      natOutgoing: Enabled

While not commonly required, there is an option to override the image prefix used, in order to download images from non-default image registries / mirrors. This came in handy for me because I could use a corporate mirror instead of the default docker.io which had strict rate limits imposed. Use it thus:

spec:
  imagePrefix: some-prefix-ending-in-fwd-slash

Then apply this edited manifest:

    kubectl create -f installation-default-edited.yaml

This would create a number of pods, including the calico API controller, calico node daemonset pods, calico typha daemonset pods, etc. The calico node daemonset pods would not be up though till the VPP dataplane is installed.

Installing VPP

To install VPP, you got to use one of two manifests, depending on whether you configured hugepages *(use https://raw.githubusercontent.com/projectcalico/vpp-dataplane/v3.24.0/yaml/generated/calico-vpp.yaml) or not (use https://raw.githubusercontent.com/projectcalico/vpp-dataplane/v3.24.0/yaml/generated/calico-vpp-nohuge.yaml). Download the appropriate YAML, and then make the following edit if needed.

The vpp_dataplane_interface attribute should be set to the name of the NIC that would be used or the node-to-node communication. By default it is set to eth1, but if that's not the interface that would be used on your node (e.g. on my cluster, I am using eth0), then set this appropriately.

Then apply:

    kubectl apply -f calico-vpp.yaml   # or calico-vpp-nohuge.yaml

This would install the calico-vpp-dataplane daemonset on the cluster nodes. If all went well, then all the pods related to calico, and the core-dns pods should be up and running in a few minutes.

Enabling IPsec

For this, the instructions here are already adequate. You need to create a secret and put a pre-shared key in it:

    kubectl -n calico-vpp-dataplane create secret generic \
    calicovpp-ipsec-secret \
    --from-literal=psk="$(dd if=/dev/urandom bs=1 count=36 2>/dev/null | base64)"

Then patch the calico-vpp-node daemonset with the ipsec configuration:

    kubectl -n calico-vpp-dataplane patch daemonset calico-vpp-node \
    --patch "$(curl https://raw.githubusercontent.com/projectcalico/vpp-dataplane/v3.24.0/yaml/components/ipsec/ipsec.yaml)"


Packet Tracing and Troubleshooting

WIP, but this is where the docs are sketchy.


Read more!

Saturday, April 22, 2023

Go virtualenvs (sort of)

Well how do you run multiple versions of the Go compiler on the same sandbox. This isn't quite the same as different virtualenvs for Python - because that is a run-time construct while this is a pure compile-time mechanism. But objectives are analogous. On a given machine, I want to be able to write Go code and build it using different versions of the Go compiler.

Assuming you already have some version of Go compiler installed, and you've set GOPATH (and GOROOT, GOBIN, etc.), here is a way to deploy additional versions of the compiler.

go install golang.org/dl/go1.17.12@latest

The above command downloads an installer binary for Go version 1.17.12 (just a random version) and places it under $GOBIN/. If you now want to install go 1.17.12, you have to run the following command.

$GOBIN/go1.17.12 download

This installs go 1.17.12 side-by-side with other versions of Go that might already be present on the box. Now, run the following command to determine the installation location.

$GOBIN/go1.17.12 env GOROOT

Use the GOROOT for the go1.17.12 installation (or whatever your chosen version is) to set environment variables. Maybe define a .goenv1.17.12 script that you can source in the shell. Each time you want to switch to this version of the Go compiler, source this script. You would need to keep your sources separate for each version I think - I am not sure if you can switch between Go versions on the same repo.


Read more!

Thursday, April 06, 2023

Distributed Tracing: A basic setup on Kubernetes

If you're trying to quickly get up to speed with distributed tracing and want to try it out in a Kubernetes environment, this post will help you set up the architectural pieces and try to see tracing in action.

Architecture

We would be running a Jaeger collector back-end that would collect all traces from everywhere. This could run outside Kubernetes too, as long as its ports are accessible from within the Kubernetes pods. Workloads generating traces would be simulated using pods running otel-cli. Each Kubernetes node would also run an OTel agent. The pods would send the traces to the agent on the local node, which in turn would forward them to the Jaeger collector.

Deployment

Deploy a recent version (>=1.35) of the Jaeger all-in-one collector for the back end, on a machine that is accessible to all the Kubernetes cluster that would be producing traces. The version is important because we want Jaeger to be capable of accepting OTLP payload which OTel libraries and agents emit. By default, it would use in-memory storage for keeping traces - they wouldn't be persistent.

docker run --name jaeger   -e COLLECTOR_OTLP_ENABLED=true   -p 16686:16686   -p 4317:4317   -p 4318:4318   jaegertracing/all-in-one:1.35

On the Kubernetes clusters where you want to run applications that generate traces, deploy OTel agent daemon sets using the following manifest.

---
apiVersion: v1
kind: ConfigMap
metadata:
  name: otel-agent-conf
  labels:
    app: opentelemetry
    component: otel-agent-conf
data:
  otel-agent-config: |
    receivers:
      otlp:
        protocols:
          grpc:
          http:
    exporters:
      otlp:
        endpoint: "192.168.219.1:4317"
        tls:
          insecure: true
        sending_queue:
          num_consumers: 4
          queue_size: 100
        retry_on_failure:
          enabled: true
    processors:
      batch:
      memory_limiter:
        # 80% of maximum memory up to 2G
        limit_mib: 400
        # 25% of limit up to 2G
        spike_limit_mib: 100
        check_interval: 5s
    extensions:
      zpages: {}
      memory_ballast:
        # Memory Ballast size should be max 1/3 to 1/2 of memory.
        size_mib: 165
    service:
      extensions: [zpages, memory_ballast]
      pipelines:
        traces:
          receivers: [otlp]
          processors: [memory_limiter, batch]
          exporters: [otlp]
---
apiVersion: apps/v1
kind: DaemonSet
metadata:
  name: otel-agent
  labels:
    app: opentelemetry
    component: otel-agent
spec:
  selector:
    matchLabels:
      app: opentelemetry
      component: otel-agent
  template:
    metadata:
      labels:
        app: opentelemetry
        component: otel-agent
    spec:
      containers:
      - command:
          - "/otelcol"
          - "--config=/conf/otel-agent-config.yaml"
        image: otel/opentelemetry-collector:0.75.0
        name: otel-agent
        resources:
          limits:
            cpu: 500m
            memory: 500Mi
          requests:
            cpu: 100m
            memory: 100Mi
        ports:
        - containerPort: 55679 # ZPages endpoint.
        - containerPort: 4317 # Default OpenTelemetry receiver port.
          hostPort: 4317
        - containerPort: 8888  # Metrics.
        volumeMounts:
        - name: otel-agent-config-vol
          mountPath: /conf
      volumes:
        - configMap:
            name: otel-agent-conf
            items:
              - key: otel-agent-config
                path: otel-agent-config.yaml
          name: otel-agent-config-vol

In the above, the address 192.168.219.1 is where the Jaeger all-in-one collector is running on my setup. Yours would be different.

Finally deploy your application which produces traces using OTel libraries and configure it to send the traces to the local node IP on port 4317. This would send the traces to the OTel agent daemon set. This section will be expanded to add Golang code samples using the OTel SDK. For now skip to the next section to see how you can test trace generation using a CLI tool.

Trying it out

Install the otel-cli in your Go build environment:

go install github.com/equinix-labs/otel-cli@latest

This would put the otel-cli binary under your $GOPATH/bin. Put this binary inside a container image, and create a pod from that image that periodically runs the following commands:

$ export OTEL_EXPORTER_OTLP_ENDPOINT=<IP>:4317
$ otel-cli exec --service my-service --name "curl google" curl https://google.com 

If you point your browser to <IP>:16686, where <IP> is the address of the machine running the Jaeger all-in-one collector, you should be able to see Jaeger UI and look up traces generated by your service.

 
 
 


Read more!

Saturday, March 25, 2023

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!

Tuesday, February 28, 2023

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!

Tuesday, February 14, 2023

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!

Sunday, December 04, 2022

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!

Friday, July 29, 2022

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!

Saturday, April 16, 2022

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!

Saturday, April 02, 2022

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!

Monday, March 14, 2022

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!

Monday, August 16, 2021

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!