Granularity of Credit and RTDS Scheduler

Granularity of Credit and RTDS Scheduler

[wy11]

Dear Xen developers,

Recently I read a paper about possible theft of service attacks in Xen  
hypervisor.

https://arxiv.org/pdf/1103.0759.pdf

Due to the 10 ms intervals between sampling points, a malicious VM is  
able to run less than a interval and sleep to avoid being accounted.

According to the info page of RTDS, it seems that after V4.7, a RTDS  
based scheduler achieves a granularity of microsecond. However, is it  
able that a VM runs for less than a microsecond and relinquish the  
host actively so as to keep its budget?

A similar problem occurs in earlier Linux kernel, and it is fixed in  
today's Linux on x86 machines by utilizing a clock source TSC with a  
granularity of nanoseconds. I'd like to know if there is any reason  
that the Xen hypervisor does not choose a nanosecond scheduler?

Thanks a lot.

Best,

Wenqiu


_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: Granularity of Credit and RTDS Scheduler

[Meng Xu]

[cc. Dario and George]

On Fri, Jan 6, 2017 at 1:34 PM, wy11 <wy11@rice.edu> wrote:
> Dear Xen developers,

Hi,

>
> Recently I read a paper about possible theft of service attacks in Xen
> hypervisor.
>
> https://arxiv.org/pdf/1103.0759.pdf

I quickly read it. It is interesting to see that EC2 suffers from such issue.
According to 4.1, it seems to me that this is more like a scheduler
"bug" in budget accounting logic.
When the attack VCPU wake up, the scheduler should starts to counting
all time consumed from now on for the attack VM, instead of the victim
VM. When the attack VCPU sleeps, the scheduler should accounts the
budget consumed for the attack VM.

In the event-driven RTDS scheduler, this issue should not happen. The
scheduler did account the budget for the correct VMs, IIRC.
Is there any experiment showing that RTDS scheduler suffers this issue?

>
> Due to the 10 ms intervals between sampling points, a malicious VM is able
> to run less than a interval and sleep to avoid being accounted.

I don't think the scheduling interval is the issue. It is more like a
budget accounting issue for me.
Dario and George may have better answer for this.

>
> According to the info page of RTDS, it seems that after V4.7, a RTDS based
> scheduler achieves a granularity of microsecond.

This is just the time granularity for users to specify the VCPU parameters.
In the scheduler, it is in nanoseconds.

> However, is it able that a
> VM runs for less than a microsecond and relinquish the host actively so as
> to keep its budget?

Nope. I don't think the attack model in the paper will succeed for the
RTDS scheduler.
If I understand the attack model correctly, it is the budget
accounting issue instead of timing granularity issue. (Please correct
me if I'm wrong).

If you have a script to show the attack on RTDS scheduler, I would be
happy to reproduce it on my machine and help fix it.

>
> A similar problem occurs in earlier Linux kernel, and it is fixed in today's
> Linux on x86 machines by utilizing a clock source TSC with a granularity of
> nanoseconds. I'd like to know if there is any reason that the Xen hypervisor
> does not choose a nanosecond scheduler?

What do you mean by a nanosecond scheduler? In the kernel, scheduler
accounts the budget in nanoseconds.

Meng


-- 
-----------
Meng Xu
PhD Student in Computer and Information Science
University of Pennsylvania
http://www.cis.upenn.edu/~mengxu/

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: Granularity of Credit and RTDS Scheduler

[Dario Faggioli]

[-- Attachment #1.1: Type: text/plain, Size: 1458 bytes --]

Il 08 gen 2017 08:31, Meng Xu <xumengpanda@gmail.com> ha scritto:
[cc. Dario and George]

On Fri, Jan 6, 2017 at 1:34 PM, wy11 <wy11@rice.edu> wrote:
> Dear Xen developers,

Hi,

>
> Recently I read a paper about possible theft of service attacks in Xen
> hypervisor.
>
> https://arxiv.org/pdf/1103.0759.pdf

I quickly read it. It is interesting to see that EC2 suffers from such issue.
According to 4.1, it seems to me that this is more like a scheduler
"bug" in budget accounting logic.

It's from March 2011. I was pretty new to Xen at the time, I'm sure George knows better.

IIRC, is that it's a known attack vector and it's been fixed. I can look at the paper and dig in the code and find proper references during during this coming week, when back from time-off, but you probably can verify it yourself, if you look carefully.

When the attack VCPU wake up, the scheduler should starts to counting
all time consumed from now on for the attack VM, instead of the victim
VM. When the attack VCPU sleeps, the scheduler should accounts the
budget consumed for the attack VM.

In the event-driven RTDS scheduler, this issue should not happen. The
scheduler did account the budget for the correct VMs, IIRC.
Is there any experiment showing that RTDS scheduler suffers this issue?

I'm sure this is not an issue for neither RTDS nor Credit2. But it's most likely not an issue any longer either for Credit.

Refards, Dario


[-- Attachment #1.2: Type: text/html, Size: 2631 bytes --]

[-- Attachment #2: Type: text/plain, Size: 127 bytes --]

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: Granularity of Credit and RTDS Scheduler

[wy11]

Thank you very much for your explanation.

To me, it seems to be an accounting problem because even if the time  
is accounted immediately a VCPU wake up or sleeps, the problem remains  
if the time is recorded in microseconds or million seconds because a  
VCPU can run for less than a unit so that the time accounted is 0.

If the time granularity of RTDS is nanosecond, then it is no longer a  
problem. Can you please help me to know where I can find it in the  
source code?

Again, thanks a lot for your help.

Best Regards,

Wenqiu


Quoting Meng Xu <xumengpanda@gmail.com>:

> [cc. Dario and George]
>
> On Fri, Jan 6, 2017 at 1:34 PM, wy11 <wy11@rice.edu> wrote:
>> Dear Xen developers,
>
> Hi,
>
>>
>> Recently I read a paper about possible theft of service attacks in Xen
>> hypervisor.
>>
>> https://arxiv.org/pdf/1103.0759.pdf
>
> I quickly read it. It is interesting to see that EC2 suffers from such issue.
> According to 4.1, it seems to me that this is more like a scheduler
> "bug" in budget accounting logic.
> When the attack VCPU wake up, the scheduler should starts to counting
> all time consumed from now on for the attack VM, instead of the victim
> VM. When the attack VCPU sleeps, the scheduler should accounts the
> budget consumed for the attack VM.
>
> In the event-driven RTDS scheduler, this issue should not happen. The
> scheduler did account the budget for the correct VMs, IIRC.
> Is there any experiment showing that RTDS scheduler suffers this issue?
>
>>
>> Due to the 10 ms intervals between sampling points, a malicious VM is able
>> to run less than a interval and sleep to avoid being accounted.
>
> I don't think the scheduling interval is the issue. It is more like a
> budget accounting issue for me.
> Dario and George may have better answer for this.
>
>>
>> According to the info page of RTDS, it seems that after V4.7, a RTDS based
>> scheduler achieves a granularity of microsecond.
>
> This is just the time granularity for users to specify the VCPU parameters.
> In the scheduler, it is in nanoseconds.
>
>> However, is it able that a
>> VM runs for less than a microsecond and relinquish the host actively so as
>> to keep its budget?
>
> Nope. I don't think the attack model in the paper will succeed for the
> RTDS scheduler.
> If I understand the attack model correctly, it is the budget
> accounting issue instead of timing granularity issue. (Please correct
> me if I'm wrong).
>
> If you have a script to show the attack on RTDS scheduler, I would be
> happy to reproduce it on my machine and help fix it.
>
>>
>> A similar problem occurs in earlier Linux kernel, and it is fixed in today's
>> Linux on x86 machines by utilizing a clock source TSC with a granularity of
>> nanoseconds. I'd like to know if there is any reason that the Xen hypervisor
>> does not choose a nanosecond scheduler?
>
> What do you mean by a nanosecond scheduler? In the kernel, scheduler
> accounts the budget in nanoseconds.
>
> Meng
>
>
> --
> -----------
> Meng Xu
> PhD Student in Computer and Information Science
> University of Pennsylvania
> http://www.cis.upenn.edu/~mengxu/
>
> !DSPAM:8895,5871ea96257295422997164!




_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: Granularity of Credit and RTDS Scheduler

[Meng Xu]

On Tue, Jan 10, 2017 at 4:32 PM, wy11 <wy11@rice.edu> wrote:
> Thank you very much for your explanation.
>
> To me, it seems to be an accounting problem because even if the time is
> accounted immediately a VCPU wake up or sleeps, the problem remains if the
> time is recorded in microseconds or million seconds because a VCPU can run
> for less than a unit so that the time accounted is 0.
>
> If the time granularity of RTDS is nanosecond, then it is no longer a
> problem.

Yep.

> Can you please help me to know where I can find it in the source
> code?

It's in burn_budget function in sched_rt.c .

>
> Again, thanks a lot for your help.

:-)

Meng

>
>
> Quoting Meng Xu <xumengpanda@gmail.com>:
>
>> [cc. Dario and George]
>>
>> On Fri, Jan 6, 2017 at 1:34 PM, wy11 <wy11@rice.edu> wrote:
>>>
>>> Dear Xen developers,
>>
>>
>> Hi,
>>
>>>
>>> Recently I read a paper about possible theft of service attacks in Xen
>>> hypervisor.
>>>
>>> https://arxiv.org/pdf/1103.0759.pdf
>>
>>
>> I quickly read it. It is interesting to see that EC2 suffers from such
>> issue.
>> According to 4.1, it seems to me that this is more like a scheduler
>> "bug" in budget accounting logic.
>> When the attack VCPU wake up, the scheduler should starts to counting
>> all time consumed from now on for the attack VM, instead of the victim
>> VM. When the attack VCPU sleeps, the scheduler should accounts the
>> budget consumed for the attack VM.
>>
>> In the event-driven RTDS scheduler, this issue should not happen. The
>> scheduler did account the budget for the correct VMs, IIRC.
>> Is there any experiment showing that RTDS scheduler suffers this issue?
>>
>>>
>>> Due to the 10 ms intervals between sampling points, a malicious VM is
>>> able
>>> to run less than a interval and sleep to avoid being accounted.
>>
>>
>> I don't think the scheduling interval is the issue. It is more like a
>> budget accounting issue for me.
>> Dario and George may have better answer for this.
>>
>>>
>>> According to the info page of RTDS, it seems that after V4.7, a RTDS
>>> based
>>> scheduler achieves a granularity of microsecond.
>>
>>
>> This is just the time granularity for users to specify the VCPU
>> parameters.
>> In the scheduler, it is in nanoseconds.
>>
>>> However, is it able that a
>>> VM runs for less than a microsecond and relinquish the host actively so
>>> as
>>> to keep its budget?
>>
>>
>> Nope. I don't think the attack model in the paper will succeed for the
>> RTDS scheduler.
>> If I understand the attack model correctly, it is the budget
>> accounting issue instead of timing granularity issue. (Please correct
>> me if I'm wrong).
>>
>> If you have a script to show the attack on RTDS scheduler, I would be
>> happy to reproduce it on my machine and help fix it.
>>
>>>
>>> A similar problem occurs in earlier Linux kernel, and it is fixed in
>>> today's
>>> Linux on x86 machines by utilizing a clock source TSC with a granularity
>>> of
>>> nanoseconds. I'd like to know if there is any reason that the Xen
>>> hypervisor
>>> does not choose a nanosecond scheduler?
>>
>>
>> What do you mean by a nanosecond scheduler? In the kernel, scheduler
>> accounts the budget in nanoseconds.
>>
>> Meng
>>
>>
>> --
>> -----------
>> Meng Xu
>> PhD Student in Computer and Information Science
>> University of Pennsylvania
>> http://www.cis.upenn.edu/~mengxu/
>>
>> !DSPAM:8895,5871ea96257295422997164!
>
>
>
>



-- 
-----------
Meng Xu
PhD Student in Computer and Information Science
University of Pennsylvania
http://www.cis.upenn.edu/~mengxu/

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: Granularity of Credit and RTDS Scheduler

[Dario Faggioli]

[-- Attachment #1.1: Type: text/plain, Size: 818 bytes --]

On Tue, 2017-01-10 at 15:32 -0600, wy11 wrote:
> If the time granularity of RTDS is nanosecond, then it is no longer
> a  
> problem. Can you please help me to know where I can find it in the  
> source code?
> 
If that's what you're interested in, time granularity is nanoseconds
for each and every scheduler.

Look at xen/common/schedule.c, xen/common/sched_credit.c,
xen/common/sched_credit2.c and xen/common/sched_rt.c, and see how they
all use the NOW() macro for reading time.

Then go checking how NOW() is defined.

Regards,
Dario
-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
-----------------------------------------------------------------
Dario Faggioli, Ph.D, http://about.me/dario.faggioli
Senior Software Engineer, Citrix Systems R&D Ltd., Cambridge (UK)

[-- Attachment #1.2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

[-- Attachment #2: Type: text/plain, Size: 127 bytes --]

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: Granularity of Credit and RTDS Scheduler

[wy11]

Thank you very much.I really appreciate your help.

Best Regards,

Wenqiu

Quoting Dario Faggioli <dario.faggioli@citrix.com>:

> On Tue, 2017-01-10 at 15:32 -0600, wy11 wrote:
>> If the time granularity of RTDS is nanosecond, then it is no longer
>> a  
>> problem. Can you please help me to know where I can find it in the  
>> source code?
>>
> If that's what you're interested in, time granularity is nanoseconds
> for each and every scheduler.
>
> Look at xen/common/schedule.c, xen/common/sched_credit.c,
> xen/common/sched_credit2.c and xen/common/sched_rt.c, and see how they
> all use the NOW() macro for reading time.
>
> Then go checking how NOW() is defined.
>
> Regards,
> Dario
> --
> <<This happens because I choose it to happen!>> (Raistlin Majere)
> -----------------------------------------------------------------
> Dario Faggioli, Ph.D, http://about.me/dario.faggioli
> Senior Software Engineer, Citrix Systems R&D Ltd., Cambridge (UK)




_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: Granularity of Credit and RTDS Scheduler

[Dario Faggioli]

[-- Attachment #1.1: Type: text/plain, Size: 1962 bytes --]

On Sun, 2017-01-08 at 22:06 +0000, Dario Faggioli wrote:
> Il 08 gen 2017 08:31, Meng Xu <xumengpanda@gmail.com> ha scritto:
> [cc. Dario and George]
> On Fri, Jan 6, 2017 at 1:34 PM, wy11 <wy11@rice.edu> wrote:
> > Recently I read a paper about possible theft of service attacks in
> Xen
> > hypervisor.
> >
> > https://arxiv.org/pdf/1103.0759.pdf
>
> IIRC, is that it's a known attack vector and it's been fixed. 
>
And it appears I was remembering right. Check commit 
78c9b2a64b38ee72cc4d3ea9e93a1a5d224ed822 "Accurate accounting for
credit scheduler", from George, in August 2009.

The changelog says:

    Rather than debit a full 10ms of credit on a scheduler tick
    (probabilistic), debit credits accurately based on time stamps.
    
    The main problem this is meant to address is an attack on the
    scheduler that allows a rogue guest to avoid ever being debited
    credits.  The basic idea is that the rogue process checks time
    (using rdtsc) periodically, and yields after 9.5ms.  Using this
    technique, a guest can "steal" 95% of the cpu.  This is
    particularly an issue in cloud environments.

So, that's the reaction to exactly the attack vector described in the
paper being found and reported, and it closes the hole by precisely
accounting how much credits a vCPU consumes.

It does it with full nanoseconds granularity, and it does it precisely.

So, the final and conclusive answer to your doubt is that _none_ of the
existing Xen scheduler (Credit, Credit2 or RTDS) are affected by the
problem described in the paper, and you can use whichever one you like,
with no fear. :-)

Regards,
Dario
-- 
<<This happens because I choose it to happen!>> (Raistlin Majere)
-----------------------------------------------------------------
Dario Faggioli, Ph.D, http://about.me/dario.faggioli
Senior Software Engineer, Citrix Systems R&D Ltd., Cambridge (UK)

[-- Attachment #1.2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 819 bytes --]

[-- Attachment #2: Type: text/plain, Size: 127 bytes --]

_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel

Re: Granularity of Credit and RTDS Scheduler

[wy11]

Thank you very much!

Best Regards,

Wenqiu

Quoting Dario Faggioli <dario.faggioli@citrix.com>:

> On Sun, 2017-01-08 at 22:06 +0000, Dario Faggioli wrote:
>> Il 08 gen 2017 08:31, Meng Xu <xumengpanda@gmail.com> ha scritto:
>> [cc. Dario and George]
>> On Fri, Jan 6, 2017 at 1:34 PM, wy11 <wy11@rice.edu> wrote:
>> > Recently I read a paper about possible theft of service attacks in
>> Xen
>> > hypervisor.
>> >
>> > https://arxiv.org/pdf/1103.0759.pdf
>>
>> IIRC, is that it's a known attack vector and it's been fixed.
>>
> And it appears I was remembering right. Check commit 
> 78c9b2a64b38ee72cc4d3ea9e93a1a5d224ed822 "Accurate accounting for
> credit scheduler", from George, in August 2009.
>
> The changelog says:
>
>     Rather than debit a full 10ms of credit on a scheduler tick
>     (probabilistic), debit credits accurately based on time stamps.
>     
>     The main problem this is meant to address is an attack on the
>     scheduler that allows a rogue guest to avoid ever being debited
>     credits.  The basic idea is that the rogue process checks time
>     (using rdtsc) periodically, and yields after 9.5ms.  Using this
>     technique, a guest can "steal" 95% of the cpu.  This is
>     particularly an issue in cloud environments.
>
> So, that's the reaction to exactly the attack vector described in the
> paper being found and reported, and it closes the hole by precisely
> accounting how much credits a vCPU consumes.
>
> It does it with full nanoseconds granularity, and it does it precisely.
>
> So, the final and conclusive answer to your doubt is that _none_ of the
> existing Xen scheduler (Credit, Credit2 or RTDS) are affected by the
> problem described in the paper, and you can use whichever one you like,
> with no fear. :-)
>
> Regards,
> Dario
> --
> <<This happens because I choose it to happen!>> (Raistlin Majere)
> -----------------------------------------------------------------
> Dario Faggioli, Ph.D, http://about.me/dario.faggioli
> Senior Software Engineer, Citrix Systems R&D Ltd., Cambridge (UK)




_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xen.org
https://lists.xen.org/xen-devel