diff --git a/build/fietsje/BUILD.bazel b/build/fietsje/BUILD.bazel
index b54b307..4a5d3fb 100644
--- a/build/fietsje/BUILD.bazel
+++ b/build/fietsje/BUILD.bazel
@@ -4,6 +4,7 @@
     name = "go_default_library",
     srcs = [
         "dependency.go",
+        "deps_cilium.go",
         "deps_containerd.go",
         "deps_gvisor.go",
         "deps_kubernetes.go",
diff --git a/build/fietsje/dependency.go b/build/fietsje/dependency.go
index c6100e4..e12e272 100644
--- a/build/fietsje/dependency.go
+++ b/build/fietsje/dependency.go
@@ -44,9 +44,22 @@
 	shelf *shelf
 
 	// Build specific settings passed to gazelle.
-	disableProtoBuild bool
-	buildTags         []string
-	patches           []string
+	disableProtoBuild    bool
+	forceBazelGeneration bool
+	buildTags            []string
+	patches              []string
+	buildExtraArgs       []string
+	// replace is an importpath that this dependency will replace. If this is set, this dependency will be visible
+	// in the build as 'importpath', but downloaded at 'replace'/'version'. This might be slighly confusing, but
+	// follows the semantics of what Gazelle exposes via 'replace' in 'go_repository'.
+	replace string
+}
+
+func (d *dependency) remoteImportpath() string {
+	if d.replace != "" {
+		return d.replace
+	}
+	return d.importpath
 }
 
 // locked is information about a dependency resolved from the go module system. It is expensive to get, and as such
@@ -73,6 +86,9 @@
 }
 
 func (d *dependency) String() string {
+	if d.replace != "" {
+		return fmt.Sprintf("%s@%s (replacing %s)", d.replace, d.version, d.importpath)
+	}
 	return fmt.Sprintf("%s@%s", d.importpath, d.version)
 }
 
@@ -86,7 +102,7 @@
 	}
 
 	// If already locked in the shelf, use that.
-	if shelved := d.shelf.get(d.importpath, d.version); shelved != nil {
+	if shelved := d.shelf.get(d.remoteImportpath(), d.version); shelved != nil {
 		d.locked = shelved
 		return nil
 	}
@@ -115,7 +131,7 @@
 	log.Printf("%s: locked to %s", d, d.locked)
 
 	// Save locked version to shelf.
-	d.shelf.put(d.importpath, d.version, d.locked)
+	d.shelf.put(d.remoteImportpath(), d.version, d.locked)
 	return d.shelf.save()
 }
 
@@ -133,7 +149,7 @@
 	}
 	goTool := filepath.Join(goroot, "bin", "go")
 
-	query := fmt.Sprintf("%s@%s", d.importpath, d.version)
+	query := fmt.Sprintf("%s@%s", d.remoteImportpath(), d.version)
 	cmd := exec.Command(goTool, "mod", "download", "-json", "--", query)
 	out, err := cmd.Output()
 	if err != nil {
diff --git a/build/fietsje/deps_cilium.go b/build/fietsje/deps_cilium.go
new file mode 100644
index 0000000..d4d9e19
--- /dev/null
+++ b/build/fietsje/deps_cilium.go
@@ -0,0 +1,78 @@
+// Copyright 2020 The Monogon Project Authors.
+//
+// SPDX-License-Identifier: Apache-2.0
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package main
+
+func depsCilium(p *planner) {
+	p.collect(
+		"github.com/cilium/cilium", "v1.8.0-rc1",
+		disabledProtoBuild,
+	).replace(
+		// Cilium forks this library to introduce an API that they need, but
+		// which the upstream rejected. Since this new API does not cause any
+		// backwards incompatibility, we pull in their fork.
+		// See https://github.com/miekg/dns/pull/949#issuecomment-487832458 for
+		// more information about the fork.
+		"github.com/miekg/dns", "github.com/cilium/dns", "8e25ec9a0ff3",
+	).replace(
+		// Cilium forks this library (a Go Kafka client) to apply the following
+		// patches on top:
+		//   - 01ce283: Fix de/serialization of null arrays
+		//   - c411825: Correcly check msgSize in ReadResp before discarding.
+		//   - 947cc36: Kafka : Cilium panics with error *index out of range
+		//              error* on receiving messages of very large size.
+		// serge@ has not found any trace of the Cilium project trying to
+		// upstream this, but the patches seem to be only bugfixes, not
+		// breaking functionality.
+		// However, the fork-off point of the upstream project is fairly old
+		// (commit b5a758db, dated Dec 7, 2017 - pre v1.5.0 of upstream). This
+		// might cause issues in the future when we start to have other
+		// consumers of this library.
+		"github.com/optiopay/kafka", "github.com/cilium/kafka", "01ce283b732b",
+	).use(
+		"github.com/hashicorp/go-immutable-radix",
+		"github.com/sasha-s/go-deadlock",
+		"github.com/google/gopacket",
+		"github.com/hashicorp/consul/api",
+		"github.com/pborman/uuid",
+		"github.com/petermattis/goid",
+		"github.com/kr/text",
+		"github.com/hashicorp/go-cleanhttp",
+		"github.com/hashicorp/serf",
+		"github.com/envoyproxy/protoc-gen-validate",
+		"github.com/hashicorp/go-rootcerts",
+		"github.com/armon/go-metrics",
+		"github.com/shirou/gopsutil",
+		"github.com/cncf/udpa/go",
+		"github.com/cpuguy83/go-md2man/v2",
+		"github.com/russross/blackfriday/v2",
+		"github.com/shurcooL/sanitized_anchor_name",
+		"github.com/google/gops",
+		"github.com/mattn/go-shellwords",
+		"github.com/c9s/goprocinfo",
+		"github.com/cilium/ipam",
+		"github.com/kardianos/osext",
+		"github.com/servak/go-fastping",
+		"github.com/golang/snappy",
+		"github.com/cilium/arping",
+	).with(disabledProtoBuild, forceBazelGeneration).use(
+		"github.com/cilium/proxy",
+	).with(disabledProtoBuild, buildExtraArgs("-exclude=src")).use(
+		// -exclude=src fixes a build issue with Gazelle. See:
+		// https://github.com/census-instrumentation/opencensus-proto/issues/200
+		"github.com/census-instrumentation/opencensus-proto",
+	)
+}
diff --git a/build/fietsje/deps_kubernetes.go b/build/fietsje/deps_kubernetes.go
index fe976b1..5fa623c 100644
--- a/build/fietsje/deps_kubernetes.go
+++ b/build/fietsje/deps_kubernetes.go
@@ -121,7 +121,6 @@
 		"github.com/robfig/cron",
 		"github.com/soheilhy/cmux",
 		"github.com/spf13/afero",
-		"github.com/spf13/cobra",
 		"github.com/spf13/pflag",
 		"github.com/tmc/grpc-websocket-proxy",
 		"github.com/vishvananda/netlink",
diff --git a/build/fietsje/main.go b/build/fietsje/main.go
index a5f8e46..373080a 100644
--- a/build/fietsje/main.go
+++ b/build/fietsje/main.go
@@ -65,6 +65,7 @@
 	depsKubernetes(p)
 	depsContainerd(p)
 	depsGVisor(p)
+	depsCilium(p)
 	depsSQLBoiler(p)
 
 	// our own deps, common
@@ -92,7 +93,7 @@
 	p.collect("github.com/kevinburke/go-bindata", "v3.16.0")
 
 	// used by deltagen
-	p.collect("github.com/lyft/protoc-gen-star", "v0.4.14")
+	p.collectOverride("github.com/lyft/protoc-gen-star", "v0.4.14")
 
 	// First generate the repositories starlark rule into memory. This is because rendering will lock all unlocked
 	// dependencies, which might take a while. If a use were to interrupt it now, they would end up with an incomplete
diff --git a/build/fietsje/planner.go b/build/fietsje/planner.go
index 4e67c2d..3aaefef 100644
--- a/build/fietsje/planner.go
+++ b/build/fietsje/planner.go
@@ -121,6 +121,24 @@
 	return c.with().use(paths...)
 }
 
+// replace injects a new dependency with a replacement importpath. This is used to reflect 'replace' stanzas in go.mod
+// files of third-party dependencies. This is not done automatically by Fietsje, as a replacement is global to the
+// entire build tree, and should be done knowingly and explicitly by configuration. The 'oldpath' importpath will be
+// visible to the build system, but will be backed at 'newpath' locked at 'version'.
+func (c *collection) replace(oldpath, newpath, version string) *collection {
+	// Ensure oldpath is in use. We want as little replacements as possible, and if it's not being used by anything,
+	// it means that we likely don't need it.
+	c.use(oldpath)
+
+	d := c.highlevel.child(oldpath, version)
+	d.replace = newpath
+	c.transitive[oldpath] = d
+	c.p.available[oldpath] = d
+	c.p.enabled[oldpath] = true
+
+	return c
+}
+
 // inject adds a dependency to a collection as if requested by the high-level dependency of the collection. This should
 // be used sparingly, for instance when high-level dependencies contain bazel code that uses some external workspaces
 // from Go modules, and those workspaces are not defined in parsed transitive dependency definitions like go.mod/sum.
@@ -170,6 +188,16 @@
 	}
 }
 
+func forceBazelGeneration(d *dependency) {
+	d.forceBazelGeneration = true
+}
+
+func buildExtraArgs(args ...string) buildOpt {
+	return func(d *dependency) {
+		d.buildExtraArgs = args
+	}
+}
+
 // use enables given dependencies defined in the collection by a high-level dependency, with any set build options.
 // After returning, the builder degrades to a collection - ie, all build options are reset.
 func (o *optionized) use(paths ...string) *collection {
diff --git a/build/fietsje/render.go b/build/fietsje/render.go
index d06e530..bc5d732 100644
--- a/build/fietsje/render.go
+++ b/build/fietsje/render.go
@@ -47,9 +47,15 @@
 		fmt.Fprintf(w, "        importpath = %q,\n", d.importpath)
 		fmt.Fprintf(w, "        version = %q,\n", d.locked.semver)
 		fmt.Fprintf(w, "        sum = %q,\n", d.locked.sum)
+		if d.replace != "" {
+			fmt.Fprintf(w, "        replace = %q,\n", d.replace)
+		}
 		if d.disableProtoBuild {
 			fmt.Fprintf(w, "        build_file_proto_mode = %q,\n", "disable")
 		}
+		if d.forceBazelGeneration {
+			fmt.Fprintf(w, "        build_file_generation = %q,\n", "on")
+		}
 		if d.buildTags != nil {
 			fmt.Fprintf(w, "        build_tags = [\n")
 			for _, tag := range d.buildTags {
@@ -65,6 +71,13 @@
 			fmt.Fprintf(w, "        ],\n")
 			fmt.Fprintf(w, "        patch_args = [%q],\n", "-p1")
 		}
+		if d.buildExtraArgs != nil {
+			fmt.Fprintf(w, "        build_extra_args = [\n")
+			for _, arg := range d.buildExtraArgs {
+				fmt.Fprintf(w, "            %q,\n", arg)
+			}
+			fmt.Fprintf(w, "        ],\n")
+		}
 
 		fmt.Fprintf(w, "    )\n")
 	}