[PATCH net 1/1 v3] net: sched: Disallow replacing of child qdisc from one parent to another

[PATCH net 1/1 v3] net: sched: Disallow replacing of child qdisc from one parent to another

[Jamal Hadi Salim]

Lion Ackermann was able to create a UAF which can be abused for privilege
escalation with the following script

Step 1. create root qdisc
tc qdisc add dev lo root handle 1:0 drr

step2. a class for packet aggregation do demonstrate uaf
tc class add dev lo classid 1:1 drr

step3. a class for nesting
tc class add dev lo classid 1:2 drr

step4. a class to graft qdisc to
tc class add dev lo classid 1:3 drr

step5.
tc qdisc add dev lo parent 1:1 handle 2:0 plug limit 1024

step6.
tc qdisc add dev lo parent 1:2 handle 3:0 drr

step7.
tc class add dev lo classid 3:1 drr

step 8.
tc qdisc add dev lo parent 3:1 handle 4:0 pfifo

step 9. Display the class/qdisc layout

tc class ls dev lo
 class drr 1:1 root leaf 2: quantum 64Kb
 class drr 1:2 root leaf 3: quantum 64Kb
 class drr 3:1 root leaf 4: quantum 64Kb

tc qdisc ls
 qdisc drr 1: dev lo root refcnt 2
 qdisc plug 2: dev lo parent 1:1
 qdisc pfifo 4: dev lo parent 3:1 limit 1000p
 qdisc drr 3: dev lo parent 1:2

step10. trigger the bug <=== prevented by this patch
tc qdisc replace dev lo parent 1:3 handle 4:0

step 11. Redisplay again the qdiscs/classes

tc class ls dev lo
 class drr 1:1 root leaf 2: quantum 64Kb
 class drr 1:2 root leaf 3: quantum 64Kb
 class drr 1:3 root leaf 4: quantum 64Kb
 class drr 3:1 root leaf 4: quantum 64Kb

tc qdisc ls
 qdisc drr 1: dev lo root refcnt 2
 qdisc plug 2: dev lo parent 1:1
 qdisc pfifo 4: dev lo parent 3:1 refcnt 2 limit 1000p
 qdisc drr 3: dev lo parent 1:2

Observe that a) parent for 4:0 does not change despite the replace request.
There can only be one parent.  b) refcount has gone up by two for 4:0 and
c) both class 1:3 and 3:1 are pointing to it.

Step 12.  send one packet to plug
echo "" | socat -u STDIN UDP4-DATAGRAM:127.0.0.1:8888,priority=$((0x10001))
step13.  send one packet to the grafted fifo
echo "" | socat -u STDIN UDP4-DATAGRAM:127.0.0.1:8888,priority=$((0x10003))

step14. lets trigger the uaf
tc class delete dev lo classid 1:3
tc class delete dev lo classid 1:1

The semantics of "replace" is for a del/add _on the same node_ and not
a delete from one node(3:1) and add to another node (1:3) as in step10.
While we could "fix" with a more complex approach there could be
consequences to expectations so the patch takes the preventive approach of
"disallow such config".

Joint work with Lion Ackermann <nnamrec@gmail.com>
Fixes: 1da177e4c3f4 ("Linux-2.6.12-rc2")
Signed-off-by: Jamal Hadi Salim <jhs@mojatatu.com>
---
 net/sched/sch_api.c | 10 ++++++++--
 1 file changed, 8 insertions(+), 2 deletions(-)

diff --git a/net/sched/sch_api.c b/net/sched/sch_api.c
index 300430b8c4d2..79e0b5c919a9 100644
--- a/net/sched/sch_api.c
+++ b/net/sched/sch_api.c
@@ -1612,7 +1612,7 @@ static int tc_modify_qdisc(struct sk_buff *skb, struct nlmsghdr *n,
 	struct nlattr *tca[TCA_MAX + 1];
 	struct net_device *dev;
 	u32 clid;
-	struct Qdisc *q, *p;
+	struct Qdisc *leaf_q, *q, *p;
 	int err;
 
 replay:
@@ -1624,7 +1624,7 @@ static int tc_modify_qdisc(struct sk_buff *skb, struct nlmsghdr *n,
 
 	tcm = nlmsg_data(n);
 	clid = tcm->tcm_parent;
-	q = p = NULL;
+	leaf_q = q = p = NULL;
 
 	dev = __dev_get_by_index(net, tcm->tcm_ifindex);
 	if (!dev)
@@ -1640,6 +1640,7 @@ static int tc_modify_qdisc(struct sk_buff *skb, struct nlmsghdr *n,
 					return -ENOENT;
 				}
 				q = qdisc_leaf(p, clid);
+				leaf_q = q;
 			} else if (dev_ingress_queue_create(dev)) {
 				q = rtnl_dereference(dev_ingress_queue(dev)->qdisc_sleeping);
 			}
@@ -1673,6 +1674,11 @@ static int tc_modify_qdisc(struct sk_buff *skb, struct nlmsghdr *n,
 					NL_SET_ERR_MSG(extack, "Invalid qdisc name");
 					return -EINVAL;
 				}
+				if (leaf_q && leaf_q->parent != q->parent) {
+					NL_SET_ERR_MSG(extack, "Invalid Parent for operation");
+					return -EINVAL;
+				}
+
 				if (q->flags & TCQ_F_INGRESS) {
 					NL_SET_ERR_MSG(extack,
 						       "Cannot regraft ingress or clsact Qdiscs");
-- 
2.34.1

Re: [PATCH net 1/1 v3] net: sched: Disallow replacing of child qdisc from one parent to another

[Jakub Kicinski]

On Sat, 11 Jan 2025 10:14:55 -0500 Jamal Hadi Salim wrote:
> The semantics of "replace" is for a del/add _on the same node_ and not
> a delete from one node(3:1) and add to another node (1:3) as in step10.
> While we could "fix" with a more complex approach there could be
> consequences to expectations so the patch takes the preventive approach of
> "disallow such config".

Your explanation reads like you want to prevent a qdisc changing
from one parent to another.

> +				if (leaf_q && leaf_q->parent != q->parent) {
> +					NL_SET_ERR_MSG(extack, "Invalid Parent for operation");
> +					return -EINVAL;
> +				}

But this test looks at the full parent path, not the major.
So the only case you allow is replacing the node.. with itself?

Did you mean to wrap these in TC_H_MAJ() || the parent comparison 
is redundant || I misunderstand?

Re: [PATCH net 1/1 v3] net: sched: Disallow replacing of child qdisc from one parent to another

[Jamal Hadi Salim]

On Tue, Jan 14, 2025 at 8:26 PM Jakub Kicinski <kuba@kernel.org> wrote:
>
> On Sat, 11 Jan 2025 10:14:55 -0500 Jamal Hadi Salim wrote:
> > The semantics of "replace" is for a del/add _on the same node_ and not
> > a delete from one node(3:1) and add to another node (1:3) as in step10.
> > While we could "fix" with a more complex approach there could be
> > consequences to expectations so the patch takes the preventive approach of
> > "disallow such config".
>
> Your explanation reads like you want to prevent a qdisc changing
> from one parent to another.
>

Yes.

> > +                             if (leaf_q && leaf_q->parent != q->parent) {
> > +                                     NL_SET_ERR_MSG(extack, "Invalid Parent for operation");
> > +                                     return -EINVAL;
> > +                             }
>
> But this test looks at the full parent path, not the major.
> So the only case you allow is replacing the node.. with itself?
>

Yes.

> Did you mean to wrap these in TC_H_MAJ() || the parent comparison
> is redundant || I misunderstand?

I may be missing something - what does TC_H_MAJ() provide?
The 3:1 and 1:3 in that example are both descendants of the same
parent. It could have been 1:3 vs 1:2 and the same rules would apply.

cheers,
jamal

Re: [PATCH net 1/1 v3] net: sched: Disallow replacing of child qdisc from one parent to another

[Jakub Kicinski]

On Wed, 15 Jan 2025 09:15:31 -0500 Jamal Hadi Salim wrote:
> > On Sat, 11 Jan 2025 10:14:55 -0500 Jamal Hadi Salim wrote:  
> > > The semantics of "replace" is for a del/add _on the same node_ and not
> > > a delete from one node(3:1) and add to another node (1:3) as in step10.
> > > While we could "fix" with a more complex approach there could be
> > > consequences to expectations so the patch takes the preventive approach of
> > > "disallow such config".  
> >
> > Your explanation reads like you want to prevent a qdisc changing
> > from one parent to another.
> 
> Yes.

In the selftest with mq Victor updated I'd say we're not changing
the parent. We replace one child of mq with another.
TC noobs would say mq is the parent.

> > > +                             if (leaf_q && leaf_q->parent != q->parent) {
> > > +                                     NL_SET_ERR_MSG(extack, "Invalid Parent for operation");
> > > +                                     return -EINVAL;
> > > +                             }  
> >
> > But this test looks at the full parent path, not the major.
> > So the only case you allow is replacing the node.. with itself?
> >  
> 
> Yes.
> 
> > Did you mean to wrap these in TC_H_MAJ() || the parent comparison
> > is redundant || I misunderstand?  
> 
> I may be missing something - what does TC_H_MAJ() provide?
> The 3:1 and 1:3 in that example are both descendants of the same
> parent. It could have been 1:3 vs 1:2 and the same rules would apply.

Let me flip the question. What qdisc movement / grafts are you intending
to still support?

From the report it sounds like we don't want to support _any_ movement 
of existing qdiscs within the hierarchy. Only purpose of graft would 
be to install a new / fresh qdisc as a child.

Re: [PATCH net 1/1 v3] net: sched: Disallow replacing of child qdisc from one parent to another

[Jamal Hadi Salim]

On Wed, Jan 15, 2025 at 9:36 AM Jakub Kicinski <kuba@kernel.org> wrote:
>
> On Wed, 15 Jan 2025 09:15:31 -0500 Jamal Hadi Salim wrote:
> > > On Sat, 11 Jan 2025 10:14:55 -0500 Jamal Hadi Salim wrote:
> > > > The semantics of "replace" is for a del/add _on the same node_ and not
> > > > a delete from one node(3:1) and add to another node (1:3) as in step10.
> > > > While we could "fix" with a more complex approach there could be
> > > > consequences to expectations so the patch takes the preventive approach of
> > > > "disallow such config".
> > >
> > > Your explanation reads like you want to prevent a qdisc changing
> > > from one parent to another.
> >
> > Yes.
>
> In the selftest with mq Victor updated I'd say we're not changing
> the parent. We replace one child of mq with another.
> TC noobs would say mq is the parent.

Yeah, Victor's test was to reduce the number of lines changed. IIRC,
there was an _child_assert which would have to change to a different
number given mq doesnt destroy the manually created qdiscs.

You can replace a queue attributes (eg queue size) or its algorithm
(example change from pfifo to bfifo) in place - that doesnt change.
What the patch avoids is taking that queue and moving it elsewhere or
having it "shared"; that puts it in the funny state that was used in
the exploit.
That was the ambiguity i was talking about in the earlier email.

> > > > +                             if (leaf_q && leaf_q->parent != q->parent) {
> > > > +                                     NL_SET_ERR_MSG(extack, "Invalid Parent for operation");
> > > > +                                     return -EINVAL;
> > > > +                             }
> > >
> > > But this test looks at the full parent path, not the major.
> > > So the only case you allow is replacing the node.. with itself?
> > >
> >
> > Yes.
> >
> > > Did you mean to wrap these in TC_H_MAJ() || the parent comparison
> > > is redundant || I misunderstand?
> >
> > I may be missing something - what does TC_H_MAJ() provide?
> > The 3:1 and 1:3 in that example are both descendants of the same
> > parent. It could have been 1:3 vs 1:2 and the same rules would apply.
>
> Let me flip the question. What qdisc movement / grafts are you intending
> to still support?
>

Grafting essentially boils down to a del/add of a qdisc. The
ambiguities: Does it mean deleting it from one hierachy point and
adding it to another point? Or does it mean not deleting it from the
first location but making it available in the other one?

> From the report it sounds like we don't want to support _any_ movement
> of existing qdiscs within the hierarchy. Only purpose of graft would
> be to install a new / fresh qdisc as a child.

That sounded like the safest approach. If there is a practical use for
moving queues around (I am not aware of any, doesnt mean there is no
practical use) then we can do the much bigger surgery.

cheers,
jamal

Re: [PATCH net 1/1 v3] net: sched: Disallow replacing of child qdisc from one parent to another

[Jakub Kicinski]

On Wed, 15 Jan 2025 09:53:27 -0500 Jamal Hadi Salim wrote:
> > > I may be missing something - what does TC_H_MAJ() provide?
> > > The 3:1 and 1:3 in that example are both descendants of the same
> > > parent. It could have been 1:3 vs 1:2 and the same rules would apply.  
> >
> > Let me flip the question. What qdisc movement / grafts are you intending
> > to still support?
> >  
> 
> Grafting essentially boils down to a del/add of a qdisc. The
> ambiguities: Does it mean deleting it from one hierachy point and
> adding it to another point? Or does it mean not deleting it from the
> first location but making it available in the other one?
> 
> > From the report it sounds like we don't want to support _any_ movement
> > of existing qdiscs within the hierarchy. Only purpose of graft would
> > be to install a new / fresh qdisc as a child.  
> 
> That sounded like the safest approach. If there is a practical use for
> moving queues around (I am not aware of any, doesnt mean there is no
> practical use) then we can do the much bigger surgery.

So coming back to the code I would have expected the patch to look
something along the lines of:

diff --git a/net/sched/sch_api.c b/net/sched/sch_api.c
index 300430b8c4d2..fac9c946a4c7 100644
--- a/net/sched/sch_api.c
+++ b/net/sched/sch_api.c
@@ -1664,6 +1664,10 @@ static int tc_modify_qdisc(struct sk_buff *skb, struct nlmsghdr *n,
 				q = qdisc_lookup(dev, tcm->tcm_handle);
 				if (!q)
 					goto create_n_graft;
+				if (q->parent != tcm->tcm_parent) {
+					NL_SET_ERR_MSG(extack, "Cannot move an existing qdisc to a different parent");
+					return -EINVAL;
+				}
 				if (n->nlmsg_flags & NLM_F_EXCL) {
 					NL_SET_ERR_MSG(extack, "Exclusivity flag on, cannot override");
 					return -EEXIST;


Whether a real (non-default) leaf already existed in that spot 
is not important..

Re: [PATCH net 1/1 v3] net: sched: Disallow replacing of child qdisc from one parent to another

[Jamal Hadi Salim]

On Wed, Jan 15, 2025 at 10:51 AM Jakub Kicinski <kuba@kernel.org> wrote:
>
> On Wed, 15 Jan 2025 09:53:27 -0500 Jamal Hadi Salim wrote:
> > > > I may be missing something - what does TC_H_MAJ() provide?
> > > > The 3:1 and 1:3 in that example are both descendants of the same
> > > > parent. It could have been 1:3 vs 1:2 and the same rules would apply.
> > >
> > > Let me flip the question. What qdisc movement / grafts are you intending
> > > to still support?
> > >
> >
> > Grafting essentially boils down to a del/add of a qdisc. The
> > ambiguities: Does it mean deleting it from one hierachy point and
> > adding it to another point? Or does it mean not deleting it from the
> > first location but making it available in the other one?
> >
> > > From the report it sounds like we don't want to support _any_ movement
> > > of existing qdiscs within the hierarchy. Only purpose of graft would
> > > be to install a new / fresh qdisc as a child.
> >
> > That sounded like the safest approach. If there is a practical use for
> > moving queues around (I am not aware of any, doesnt mean there is no
> > practical use) then we can do the much bigger surgery.
>
> So coming back to the code I would have expected the patch to look
> something along the lines of:
>
> diff --git a/net/sched/sch_api.c b/net/sched/sch_api.c
> index 300430b8c4d2..fac9c946a4c7 100644
> --- a/net/sched/sch_api.c
> +++ b/net/sched/sch_api.c
> @@ -1664,6 +1664,10 @@ static int tc_modify_qdisc(struct sk_buff *skb, struct nlmsghdr *n,
>                                 q = qdisc_lookup(dev, tcm->tcm_handle);
>                                 if (!q)
>                                         goto create_n_graft;
> +                               if (q->parent != tcm->tcm_parent) {
> +                                       NL_SET_ERR_MSG(extack, "Cannot move an existing qdisc to a different parent");
> +                                       return -EINVAL;
> +                               }

Yes, this should work as well - doesnt have to save the leaf_q, so more optimal.
Please send the patch.

cheers,
jamal
>                                 if (n->nlmsg_flags & NLM_F_EXCL) {
>                                         NL_SET_ERR_MSG(extack, "Exclusivity flag on, cannot override");
>                                         return -EEXIST;
>
>
> Whether a real (non-default) leaf already existed in that spot
> is not important..

Re: [PATCH net 1/1 v3] net: sched: Disallow replacing of child qdisc from one parent to another

[Jakub Kicinski]

On Wed, 15 Jan 2025 15:39:43 -0500 Jamal Hadi Salim wrote:
> > diff --git a/net/sched/sch_api.c b/net/sched/sch_api.c
> > index 300430b8c4d2..fac9c946a4c7 100644
> > --- a/net/sched/sch_api.c
> > +++ b/net/sched/sch_api.c
> > @@ -1664,6 +1664,10 @@ static int tc_modify_qdisc(struct sk_buff *skb, struct nlmsghdr *n,
> >                                 q = qdisc_lookup(dev, tcm->tcm_handle);
> >                                 if (!q)
> >                                         goto create_n_graft;
> > +                               if (q->parent != tcm->tcm_parent) {
> > +                                       NL_SET_ERR_MSG(extack, "Cannot move an existing qdisc to a different parent");
> > +                                       return -EINVAL;
> > +                               }  
> 
> Yes, this should work as well - doesnt have to save the leaf_q, so more optimal.
> Please send the patch.

I'm gonna keep your commit and just post a v4, hope that's okay.

Re: [PATCH net 1/1 v3] net: sched: Disallow replacing of child qdisc from one parent to another

[Jamal Hadi Salim]

On Wed, Jan 15, 2025 at 8:33 PM Jakub Kicinski <kuba@kernel.org> wrote:
>
> On Wed, 15 Jan 2025 15:39:43 -0500 Jamal Hadi Salim wrote:
> > > diff --git a/net/sched/sch_api.c b/net/sched/sch_api.c
> > > index 300430b8c4d2..fac9c946a4c7 100644
> > > --- a/net/sched/sch_api.c
> > > +++ b/net/sched/sch_api.c
> > > @@ -1664,6 +1664,10 @@ static int tc_modify_qdisc(struct sk_buff *skb, struct nlmsghdr *n,
> > >                                 q = qdisc_lookup(dev, tcm->tcm_handle);
> > >                                 if (!q)
> > >                                         goto create_n_graft;
> > > +                               if (q->parent != tcm->tcm_parent) {
> > > +                                       NL_SET_ERR_MSG(extack, "Cannot move an existing qdisc to a different parent");
> > > +                                       return -EINVAL;
> > > +                               }
> >
> > Yes, this should work as well - doesnt have to save the leaf_q, so more optimal.
> > Please send the patch.
>
> I'm gonna keep your commit and just post a v4, hope that's okay.

Thanks!

cheers,
jamal